Sandbox for Proposed Challenges

Question

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Comments addressing specific points mentioned in the proposal
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Answer 1

Traffic Troubles

king-of-the-hill

Background

Consider the following grid:

    a   b   c
    |   |   |
    |   |   |
    |   |   |
d---+---+---+---e
    |1  |2  |3
    |   |   |
    |   |   |
f---+---+---+---g
    |4  |5  |6
    |   |   |
    |   |   |
h---+---+---+---i
    |7  |8  |9
    |   |   |
    |   |   |
    j   k   l

I've marked every endpoint with a letter a-l, and every + with a number 1-9. Imagine, for a moment, that this grid represents a small section of a town. Each | or - represents one segment of a two-way road, and each + represents an intersection, which will have a corresponding stoplight.

During the game, cars will be added and removed from the grid at the endpoints a-l. Cars move exactly one space (through one segment of road or through one intersection) per turn, and never change direction. Thus, if a car enters the grid at endpoint d, it will exit after reaching endpoint e. We may assume that the cars are smart enough to avoid all collisions. They will never move to a space occupied by another vehicle, and they will never enter an intersection when the stoplight they see is red. When a car reaches the opposite endpoint, it disappears and can be safely forgotten.

Assume that we have a variable entitled public_unhappiness that is initialized to 0.

If a car following the above rules may not move due to another vehicle or a stoplight, the value of public_unhappiness is increased by 1.

//SANDBOX NOTE: This formula is linear, but one could say that unhappiness goes up exponentially the longer you sit at a stoplight. This formula is subject to change.

We pit two bots against each other, both controlling traffic flow in different ways. One bot aims to maximize public_unhappiness and the other aims to minimize it. We will refer to the former as The Driver and the latter as The Traffic Engineer. Because this KotH is inherently unbalanced, Drivers and Traffic Engineers will face off in a round-robin tournament (playing only against the opposing faction) and will be placed in separate leaderboards.

Input

Though the bots are different and rely on entirely different strategies, every bot has access to the same information. Every turn, the bots will be prompted with a list of command-line arguments. Below is a general format:

./Traffic_Troubles Your_bot.extension S1 S2 S3 S4 S5 S6 S7 S8 S9 N a,b,c a,b,c ...

S1 through S9 are binary digits that represent what direction traffic may flow through the corresponding stoplight. If the value is 1, traffic flows horizontally through this stoplight. If the value is 0, traffic flows vertically. Hence, a car approaching intersection 1 from the east will stop moving if the value of S1 is a 0, and continue moving along if that value is a 1.

The following argument is N. This represents the number of cars currently active on the board.

There then follows N descriptions of cars in the form a,b,c. Here, a is the character of the endpoint that a car originated, b is its destination, and c is the number of spaces it has moved. A car that has just been put on endpoint a has moved 0 spaces, and would thusly be described as a,j,0. On the other hand, a car approaching intersection 6 from the west would be described as f,g,11.

On the first turn, every stoplight has value 0, and no cars exist on the board (N == 0).

//SANDBOX NOTE: This input seems pretty messy... Any ideas?

The Traffic Engineer

Traffic Engineers aim to minimize public_unhappiness by changing the values of the stoplights to allow for traffic to continue through.

You may specify the values of up to three stoplights per turn. Every turn your bot is called, you must provide up to 3 space-separated output pairs of the form a,b where a is the number of the spotlight you want to change, and b will be a binary digit representing the desired value of the stoplight. Invalid output will count as a change to the stoplights, but be ignored. You may choose to output any number of changes less than or equal to 3.

//SANDBOX NOTE: The value of 3 is subject to change.

The Driver

Drivers aim to maximize public_unhappiness by choosing entry points for cars.

Every turn, you may output up to six distinct entry points for cars in the form X Y Z .... If a car already exists on that entry point and is not moving in the opposite direction that output will be ignored. You may specify any number of entry points less than or equal to 6.

//SANDBOX NOTE: The number 6 is subject to change

The Sequence of Events

1. Both bots are called at roughly the same time with access to the exact same information.

2. Cars are added to the entry points and the value of stoplights are changed.

3. Cars move, and public_unhappiness is incremented accordingly.

4. Any car that has surpassed its respective exit point is removed from play.

//SANDBOX NOTE: Perhaps the Traffic Engineer should be able to view where the Driver put cars and adjust accordingly. Thoughts?

Rules

1. Your bot is given 1 second to respond.

2. You may not tailor your bot to act specifically against another bot.

3. Please provide a method for compiling your bot and a command-line method for running your bot.

4. The header of your answer should be in this format:

   [Language-name] - [Traffic Engineer/Driver] - [Bot-name]

5. Standard Loopholes are disallowed.

//SANDBOX NOTE: If this idea is received well (~4-6 upvotes on the sandbox) I will build the controller. For now, it's just an idea. If you wish to run/improve on this KotH, you are welcome to.

Answer 2

8-FTU - Retrofit UTF-8 to any pre-1988 language

code-golf

The design of Unicode started in 1987 and was first published in 1988. UTF-8 itself was designed in 1992 and first presented in 1993. Your goal is to retrofit the UTF-8 encoding of Unicode to any language that was in existence on 31 December 1987. You can't use any features that were added to the language after this date.

Your program will take a text input (byte encoded characters, possibly with errors) and up to two integers. Your program must accept any value at any byte position (00-FF).

Task 1 - Validate the input

Your program will print one of TRUE/FALSE, True/False or true/false depending on whether the text is valid UTF-8 or not, and exit if the format is not valid. See below for validation rules. There are also many online resources that cover the format that you can reference.

Task 2 - Count the code points

If your program didn't exit at the end of Task 1, it will print the number of Unicode code points encoded within the text.

Task 3 - Substring

Using the two integer inputs your program will find and output the matching substring. The first integer will be the starting position, 0 will be the start of the string. If the starting position is after the end of the string, return an empty string. The second integer will be the length of the substring in Unicode code points. If the length is omitted or goes past the end of the string return all the text from the start position to the end of the string. You do not need to program for negative numbers, although you can if you want to.

Tasks 1 & 2 must be printed to standard output. If printing the output of Task 3 would have undesirable consequences (e.g. characters interpreted as control codes) you may return the text instead. You don't have to worry about how the text will display, your code will be taken by DeLorean or TARDIS (depending on country) to 1987 or earlier where a team of engineers will work on displaying it correctly!

Valid encodings

  Code points        Byte encoding
---------------    -----------------
U+0000 - U+007F    Standard 7-bit ASCII (00 - 7F)
U+0080 - U+07FF    Two bytes per code point (C2 80 - DF BF)
U+0800 - U+D7FF    Three bytes per code point (E0 A0 00 - ED 9F BF)
U+D800 - U+DFFF    High and low surrogate pairs, invalid in UTF-8 (ED A0 80 - ED BF BF)
U+E000 - U+FFFF    Three bytes per code point (EE 80 80 - EF BF BF)
U+010000 - U+10FFFF    Four bytes per code point (F0 80 80 80 - F4 8F BF BF)

Byte table

• 00 - 7F: Standard 7-bit ASCII
• 80 - BF: Continuation bytes
• C0 - C1: Invalid - Task 1 must print one of the false messages if either of these bytes are present
• C2 - DF: Start of two-byte code
• E0 - EF: Start of three-byte code. ED codes where the next byte is one of A0-BF are invalid because they encode surrogate pairs
• F0 - F4: Start of four-byte code. Note: not all sequences starting with F4 are valid. You need to test for these too
• F5 - FF: Invalid - Task 1 must print one of the false messages if any of these bytes are present

The remainder of a multi-byte code must only be continuation bytes until the length is reached. E.g. E4 85 B9 is valid because E4 marks the start of a three byte code, there are exactly three bytes and 85 and B9 are both within the range 80-BF. A continuation byte must not appear except as part of a multi-byte sequence, which must start with C2-F4. Long encodings are not allowed. E.g. "A" is 41, which could also be encoded as C1 81 or E0 81 81. These longer sequences are invalid because there is a shorter, valid sequence.

You don't need to worry about the BOM code point U+FEFF (EF BB BF). Treat it as any other character even if it appears within the text.

Example input (to be expanded)

C3 87 61 20 76 61 3F 0 2 (Ça va?, 7 bytes, 6 code points)

Outputs:

True
6
Ça

C3 87 61 20 76 61 3F 2 (Ça va?, 7 bytes, 6 code points)

Outputs:

True
6
 va?

C1 87 61 20 76 61 3F 0 2 (Ga va?, 7 bytes (overlong error), 6 code points)

Outputs:

False

As mentioned above, the output for Task 3 may be returned as a string instead of printing it.

Scoring

Either shortest code in bytes or a bonus awarded for retrofitting an older language. Maybe bytes minus the number of months before January 1988, assuming a release date of December if not otherwise specified?

Answer 3

KotHgress

king-of-the-hill

As everyone knows, the only way to make sure your voice is heard among a group of people is to shout louder than everyone else. This is especially true in KotHgress, a bureaucratic committee of PPCG bots.

The KotHgress Register is a 1D string, at least 100 characters long, containing the minutes of each committee meeting. The only problem is that all the committee members talk at the same time, often shouting over each other, so that (like a typical committee), nothing ever gets done. However, since this is a committee of bots, efficiency is prized almost as much as volume.

Rules

The Register for each meeting is a string of length max(100, N_bot * 4). At the beginning of each meeting, a committee member bot is pseudorandomly assigned an ascii character to be its voice, and 3 starting positions for its voice in the Register (initial index of 1), with each bot's positions having the same sum - for example, [1,4,100] and [5, 25, 75] could be starting positions.

Each turn, a bot receives 20 points times the number of times its voice appears in the Register. The bot can spend any amount of its points to bid on positions in which to place its voice. A bot that does not spend all its points banks any remaining points towards its score for the round; points do not carry over to following rounds.

Once all bids have been collected, each position is overwritten with the voice of the highest bidder, with ties for high bid causing no change in that position's current character. Note: a bot that is outbid for a position it already occupies loses that position.

Then, each bot accumulates score equal to the combined rank of its voice characters in the Register (for example, "ABABB" would score 4 for "A" at rank 1 and 3, and 11 for "B" at rank 2, 4, and 5), and the Register is sent as input to each member for them to choose their next bids.

After 100 turns, the meeting is over, and the bot with the highest accumulated score wins the meeting.

Input

Each turn, bot will receive four inputs, in this order:

1. a single character which is its voice
2. a positive integer indicating its current (banked) score
3. a positive integer indicating the number of points it collected this turn
4. a string of length max(100, N_bot * 4), the Register

Output

The bot should output a string consisting of integer pairs, separated like so: "pos0 bid0|pos1 bid1|...|posM bidM". Banked points will be automatically calculated from the output: banked_points = turn_points - sum(bids).

Invalid output, including sum(bids) > turn_points, will cause your bot to lose its turn (not banking any points).

Meta-notes

• Controller construction is in progress.
• I expect it to be language-agnostic (using a similar setup to aBOTcalypse). Bots will be allowed one storage file for memory purposes.

Answer 4

Time Travel in KotH

This is not a question but a possible mechanic for KotH (king-of-the-hilltype challenge).

In KotH we can ask each program (player) to store all its memory in a file between steps. This makes it possible to change a player's memory to an older one which is not possible with human players. This fact makes it possible to crate time-traveling based games.

I will outline to mechanics here, a simpler one (Time Reverters) and a more complex one (Time Travelers). Both will use a simple game to show how they would work.

Time Reverters (mechanic I)

A very simple example game

• Two players, N rounds.
• At every round a random player scores a point.
• The winner is the player with more points after round N.

The time reverse twist

• At any time in the game a player can chose to time travel (TT) back to any previous round. This means the players will receive the memory they had at that round and forget everything else. Neither of them will know a TT happened.
• Each player can TT K times and this is counted by the controller. If a player tries to travel when it has no more travels left, the TT request is simply ignored.

Time Travellers (mechanic II)

(will be written later...)

Answer 5

Split multi-language no-space sentences

You will be given a string representing a sentence without word any boundaries. Additionally, you're given a dictionary of all possible words. Output all possible possible ways of splitting the sentence into words.

But there's a catch! The sentence was written by a drunken polyglot and contains words from multiple languages mixed together. Luckily, you've already got a dictionary of which words from different languages cirrespond to each other. So for each word, you should output its surface form (as it appears in the input sentence) and base form (eg. English). To prevent meaningless interpretations of a sentence as many one-letter words and abbreviations, sort the output by the number of words of each interpretation, lowest first.

Example:

teeistunnationalgetränkdeeikoku

tee/tea ist/is un/a national/national getränk/drink de/of eikoku/england

Given the dictionary below, the first word can only be tee, German for tea. Then comes is, which is already the English is. Then un, French for a. And so on.

tea => tea, tee, cha

is => is, ist, est, dess

a => a, ein, un, une, aru

national => national, kokkateki

drink => drink, getränk, nomimono

of => of, de, von, no

england => england, angleterre, igirisu, eikoku

Each entry of the dictionary is of the form:

<base_form> => <surface_form_1>, <surface_form_2>, ...

That is, the dictionary contains the base form (here English is used), and a list of possible variations in different languages for each.

See below for examples with multiple possibilities.

Scoring

Code-golf.

(Golfed explanation. Ungolfed: The answer with the shortest code as measured by its bytesize in an encoding the interpreter or compiler accepts without additional flags wins. Multiple files add a penalty of 1 byte for each additional file. Flags add to the score.)

Rules

• The defaults apply, function or program.
• You may assume there exists at least one solution.
• Your program must run in a reasonable amount of time, so don't just try every possible combination of words. Be prepared for a dictionary that contains hundred or thousands of words. Let's say about ~10 minutes on a modern PC.
• You must support unicode, at least the basic multi-lingual plane, codepoints 0x0000 - 0xFFFF. If your language of choice does not support unicode, you can emulate it using a fixed-length unicode encoding: consider each n bytes of the input sentence a letter.
• You do not need to worry about unicode modifiers, normalizing etc. -- each codepoint is considered a unique "letter".

Input

• The defaults apply, stdin, command line argument, function argument, javascript prompt etc.
• The input sentence is given as a string (teaist) or list/array ([t,e,a,i,s,t])
• You may assume the input sentence is already in lower case.
• There is no additional punctuation in the input sentence to take care of.
• However, the input sentence and the dictionary may contain "words" with commas, periods, etc., ie. every unicode codepoint from the basic multilingual plane. It will not contain any of the codepoints 0x00-0x20, which means no null-bytes, spaces, tabs, newlines, so you can use them for separating the output.
• The dictionary may be in any format of your choice, but it must contain an association between a base form and all possible surface forms. It must not list all base forms for each surface form.
• You may also read the dictionary from a file, and take the file name or raw data as input.
• You may also assume the dictionary has already been stored in one variable of your choice. If you do, please provide some code for reference how I can put custom data in it, or read the dictionary from a file. However, it must not be pre-processed and as close to a hash (eg. {<base_form> => [ <surface_form_1>, <surface_form_2>, ... }) or array/list (eg. [ [<base_form>,<surface_form_1>,<surface_form_2>,...], [<base_form>,...], ...]) as possible in your language.
• You may choose whether the list of surface forms includes the base form or not, eg. big => big, gross or big => gross.

Output

• The defaults apply, stdout, stderr, return value, javascript alert, etc.
• It should not need to be said, but if you output to stderr, nothing else but the solution must go to stderr, unless it's a compiler/interpreter warning that can be turned off by a flag.
• A list/array of all possible interpretations of splitting the sentence into words, sorted by the number of words.
• Each interpretation is a list/array of words. Each word is pair/list/array containing the surface form and the base, you may choose in which order. The words must be ordered as they appear in the input sentence.
• Alternatively, the array may be flattened.
• Alternatively, output two lists/arrays, one containing the base form for each word, and one the surface form.
• Alternatively, output a string representation of the array/hash/list.

For example, you could output an array

[["tee","tea"],["est","is"]]

or a flattened array

["tee","tea","est","is"]

or two arrays

["tee","est"]

["tea","is"]

or a string representation such as tee:tea:est:is or tee\ttea\nest\tis\n (\t tab, \n newline). But make sure you're escaping characters properly.

Test cases:

First line is the input string. Each following line is a possible way of placing word boundaries, surface/base. Afterwards a sample dictionary is provided.

1

Note that some words contain a semi-colon.

abcd;efghi

ab/test cd;ef/awesome ghi/result

a/only bcd/test ;ef/awesome ghi/result

abcd;efgh/yahoo i/google

with the dictionary:

test: ab, bcd

awesome: cd;ef, ;ef

result: ghi

only: a

yahoo: abcd;efgh

google: i

2

sumomouserune

sumo/sumo mouse/mouse rune/rune

sumomo/plum useru/lose ne/right

with the dictionary:

sumo: sumo, mouse:mouse, rune: rune, plum: sumomo, lose: useru, right: ne

3

koukousensei

koukou/school sensei/teacher

koukou/shiptravel sensei/starfortunetelling

with the dictionary

school: koukou, teacher: sensei, shiptravel: koukou, starfortunetelling: sensei

4

unicode support:

白雲

白/sira 雲/kumo

白/haku 雲/uñ

with the dictionary:

sira:白, haku:白, kumo:雲, uñ:雲

5

Note the order of the results.

aaaa

aaaa/test

a/test aaa/test

aa/test aa/test

aaa/test a/test

a/test a/test aa/test

a/test aa/test a/test

aa/test a/test a/test

a/test a/test a/test a/test

with the dictionary:

test: a, aa, aaa, aaaa

I'll add a larger example should I post this.

Answer 6

Snake vs labyrinth

Write a program that takes as input a text file representing a labyrinth and checks if this labyrinth can be entirely filled with a snake path. The program should output true or 1 if this is the case, false or 0 else.

The snake can enter the labyrinth at any point. He can move one cell up, left, right or down; once he has crossed a cell of the grid, he cannot go back to that cell. The snake cannot cross a wall or the borders of the labyrinth.

The labyrinth file is a grid of m x n characters, containing either # (wall) or . (empty space).

Example 1

should return true

.

Example 2

should return true

..
..

Possible solution (S = snake start, E = snake end, v = go down, < = go left)

Sv
E<

Example 3

should return true

...
.#.
...

Possible solution (S = snake start, E = snake end, v = go down, < = go left, > = go right, ^ = go up)

S>v
E#v
^<<

Example 4

should return false

.#
#.

Example 5

should return false

#.#
...

Example 6

should return false

.#.
...
...

This is code-golf, so the shortest code wins.

Answer 7

Given an input, calculate the correct suffix and output the number in a readable format. The suffixes must go to at least 10^3000, in which the rules for calculating them can be found here, or a list can be found here.

For example:

10000 = 10.0 thousand
135933445 = 135.93 million
-2 = -2.0
-2.36734603 = -2.37
'1'+'9'*3000 = 2.0 nongennovemnonagintillion

Rules:

• No getting things from external resources - it must all be calculated within the code.
• External modules are fine as long as it doesn't breach the above rule.
• The input should work when input as a string, integer or float.
• The output must always contain a decimal place.
• The output must be rounded if above 2 decimal places.
• Leaving zeroes at the end is optional, as long as it doesn't go above 2 decimals (1.00 or 1.0 are both fine) and is consistent for all inputs (1 should output the same as 1.0).
• Must not throw an error no matter how high or low the input is.

Scoring:

• Score is the length of the code, including indents.
• Lowest score wins.
• It does not need to be a function, printing the output is fine.

As a starting point, here is an ungolfed version of some code to generate the list of suffixes. Feel free to build upon this or start from scratch.

a = ['', 'un','duo','tre','quattor','quin','sex','septen','octo','novem']
c = ['tillion', 'decillion', 'vigintillion', 'trigintillion', 'quadragintillion', 'quinquagintillion', 'sexagintillion', 'septuagintillion', 'octogintillion', 'nonagintillion']
d = ['', 'cen', 'duocen', 'trecen', 'quadringen', 'quingen', 'sescen', 'septingen', 'octingen', 'nongen']

num_dict = ['']
num_dict.append('thousand')
num_dict.append('million')
num_dict.append('billion')
num_dict.append('trillion')
num_dict.append('quadrillion')
num_dict.append('quintillion')
num_dict.append('sextillion')
num_dict.append('septillion')
num_dict.append('octillion')
num_dict.append('nonillion')

for prefix_hundreds in d:

    #tillion can't be used first time round
    if not prefix_hundreds:
        b = c[1:]
    else:
        b = c

    for prefix_tens in b:
        for prefix in a:
            num_dict.append(prefix_hundreds+prefix+prefix_tens)

For the record, my result is 578 characters. To be fair I'm surprised I couldn't find this being asked before :P

Answer 8

Code Bots ϕ

This is a challenge based on the popular Code Bots ("What's wrong with public variables?") challenge.

I made a few observations during the development of the original Code Bots:

1. I had a literal ton of ideas and wouldn't stop harassing Nathan Merrill about them.
2. Nathan Merrill already claimed Code Bots 2.

The solution is obvious: make my own challenge. So, that is exactly what I intend to do.

Note: I am working on various ways to distinguish the two challenges.

Variables

Note: I have changed the names of some variables to make them more "intuitive."

The variables A and B each store an integer 0-23.

The variable C (for Control) stores an integer 0-23 and is incremented at the end of every turn. It indicates which line of the program is to be executed.

The variable D (for Direction) stores and integer 0-23, which determines the current direction of the bot. The direction is determined by {north east south west}[[D % 4]].

The variable E (for Entropy) is overwritten by a random integer at the end of each turn, but only if your bot uses it that turn.

The variable F (for Feeling) provides a sense of touch. This allows you to detect when a bot is next to you. The value equals the number of adjacent bots. For example, F equals 4 when you are completely surrounded on all four sides (and thus out of luck).

The variable G (for aGe) provides a timer. The value is incremented after the end of every turn, mod 24. This allows an easy way to do for-like loops.

Instructions

Each line contains a single command, and each command takes a variety of arguments.

Flag : This represents your flag. Your goal is to smear your flag across the known universe. Each flag line has a hidden identifier denoting the owner. These lines do nothing upon execution.

Move : This moves the bot 1 unit forward in the direction that it is facing.

Copy [expr|line] [var|line] : This copies one expression to another. Both expressions must be of the same type. You can copy a line to another line or copy the value of one variable to another. Copying to yourself has a new advantage in that, instead of making an immediate change, the change is made just prior to the start of your next turn.

Copy2 [expr|line] [var|line] : This is a new version of copy, but instead of performing the action immediately after your turn, it performs the action immediately before your next turn. [todo: find a better name for it. Maybe "DelayCopy"]

If [cond] [line] [line] : This is an If statement, one of the most important statements. If the conditional evaluates to true, then the first of the two lines is executed immediately afterwards (on the same turn). If the conditional is false, then the second line is executed immediately afterwards. In order to prevent infinite loops of various kinds, a bot is not allowed to execute the same line twice in a single turn.

Jump [expr] [cond] : This is a new instruction designed to help speed up bots. Given a number N, it immediately sets the value of C to N and then executes #N on the same turn. The condition is optional, but if present it will determine whether or not the Jump command is executed or not.

Block [var|line] : This blocks a certain variable or line. Each variable or line can be blocked once, and this block prevents one modification attempt of that variable/line. If an opponent (or yourself) attempts to modify that variable, then the variable is merely unblocked rather than modified.

Arguments

There are four types of arguments, var, line, expr, and cond. Here are their relationships:

 var = *[var] | A | B | C | D | E
expr = [var] | [expr][op][expr] | [literal number]
 op = + | - | %
line = *[line] | #[expr]
cond = [expr] | [line] | [expr]=[expr] | [expr]==[expr] | [line]=[line] | [line]==[line]

There are three types of operators which can be used in expressions: Addition +, Subtraction -, and Modulo %. The modulo operator has highest preference (left to right), with addition/subtraction being applied afterwards.

There are several different kinds of conditionals.

1. If [expr] usually returns true if the value of the expression is non-zero. There are several special cases. If D returns true if there is a bot directly in front of you. If E returns true if E is odd. (Note: add more special cases)

2. If [line] returns true if the line contains a flag.

3. If [expr]=[expr] returns true if the two expressions are equal mod 4.

4. If [line]=[line] returns true if the two lines are the same type (same command).

5. If [expr]==[expr] returns true if both expressions are equal mod 24.

6. If [line]==[line] returns true if the two lines are exactly equal (such as both flags having the same owner).

The Turn Structure

(Initially, all variables are 0 except for E)
[command execution starts]
The command at line #C is executed.
If there is a chain of logic, it is followed until it stops or a line is visited twice.
[updates]
The effect of a Copy statement is applied, if any.
C is incremented
If needed, E is randomized.
(other bot's turns here)
F is updated
The effect of a Copy2 statement is applied, if any.
[next command execution]

Line Labels

To increase the ease of writing bots, there will be new things called line labels, which look like this word: and can be placed at the start of a line. Later in the code, you can reference the line label like this :word. (Note: The exact formatting is up for discussion).

During preprocessing, the controller will replace all instances of :word with the number of the line labeled word:. If the :word label is the only thing on the line (no command) then the entire line will be copied into that blank line. Here is an example:

main: If D #:move #:attack
:main
:main
Jump :main
move: Move
attack: Copy #:flag *#*C

Other usability features

The language will be completely case-insensitive. Comments will take the form of //comment.

The Arena

There will be 50 bots of each type entered into an arena. Initially, all of the bots will be evenly spaced on a grid and facing north.

....@.......@.......
.......@.......@....
..@.......@.......@.
.....@.......@......
@.......@.......@...
...@.......@.......@
......@.......@.....
.@.......@.......@..

Note: I believe this to be an improvement because the bots are not directly lined up with each other. In Code Bots 1, a bot could Move on its first turn and end up right behind another bot. In this grid, a bot has a much smaller chance of

A complicated example bot

Each bot can contain up to 24 lines, and each line contains an instruction. If there are any blank lines (after substitution with line labels), then those lines are filled by Flags.

main: If D #:attackloop #:move        //attack if an opponent 
:main                             //automatically filled in with the same line
loop: jump :main                  //executes line 0 again and sets C to 0
move: if T #:run #:turn           //always move (never rotate) when being attacked
run: Move
turn: If E #:run #:turn2          //randomly pick move or rotate
turn2: Copy2 D+1 D
attackloop: jump :attack
attack: Copy #:freeze *#*C         //freeze the opponent
plant: Copy #C+6 *#E              //plant your flag
:plant
:plant
:plant
Jump :loop                        //return to main loop
freeze: Copy2 C-1 C             //this creates an endless loop when executed

After preprocessing, the above bot turns into the bot below. You can also simply submit the bot below without using any line labels if you'd like.

If D #8 #3
If D #8 #3
Jump 0
If T #4 #5
Move
If E #4 #6 
Copy2 D+1 D
Jump 9
Copy #14 *#*C
Copy #C+6 *#E
Copy #C+6 *#E
Copy #C+6 *#E
Copy #C+6 *#E
Jump 2
Copy2 C-1 C
Flag
Flag
Flag
Flag
Flag
Flag
Flag
Flag
Flag

Short, Useful Code Snippets

Block #G
Jump 0 G   //block all the lines in 24 moves

Answer 9

A covering array is an N by k array in which each element is one of {0, 1, ..., v-1} (so v symbols in total), and for any t columns chosen (so an N x t array) contains all possible v^t tuples.

Input: N, k, t, v (all 4 are positive integers), and then N x k integers, each of which comes from {0, ..., v-1}. Each of the integers are separated by spaces.

Output: Yes if the input is a valid covering array, and No if it is not.

Goal: in any language you want, write a program that validates if the input is a covering array in the fastest time. I will run programs on my machine, which is a Macbook Pro 2.2 Ghz Intel i7 with 16 GB RAM.

Answer 10

KOTH Simpleton's Chess

Introduction

Disclaimer: The word "simpleton" is not meant to offend anyone who is simple or anything else. Don't take it personally, please.

It is a lovely afternoon at the Completely Average Chess Club, and like most afternoons, the chess players, who are also part-time code golfers, are golfing programs to play chess. They use incredibly complicated move-finding algorithms and are golfing them down into 4 byte programs. However, on this particular afternoon, some aliens, who are looking to use human intelligence to play alien chess, steal the chess players' intelligence, turning them into simpletons! Now they can't even remember all the pieces, let alone perform an alpha-beta tree-search.

Today, we won't be focusing on restoring the chess players' minds back. Instead, we'll be playing a modified chess game with simpler rules!

Rules

The pieces

Like regular chess, Simpleton Chess has two teams: white and black. Unlike regular chess, however, Simpleton Chess only has one piece that can attack north, north west and north east and can move two squares at a time. If you are familiar with regular chess, this is much like the pawn except for the fact you can attack forward (or north) and can move two squares at a time. Like regular chess, to take a piece you must move in the place of the piece that you wish to take. If there is a piece in of you, and you move 1 square in front, then you will take that piece.

Castling and en passant are ignored.

Winning the game

To win the game, you must take all the pieces of the opposing team.

Time limit

Each entry has an allowed time is 3 minutes (180000ms).

The board

Any piece that moves outside the board will disqualify you. The board is a 2D int array that you can access by assigning a variable to SimpletonUtils.read

Entries

Your entry is expected to have two methods: getName() and move().

The getName() method will return a String of the name of your entry.

The move method is a void and is called every time you need to move.

To submit the board you use SimpletonUtils.submitBoard

Entries are suggested (and very, very much encouraged) to verify the board using SimpletonUtils.verifyBoard (you have 3 minutes, no need to worry about speed). You will be disqualified if you submit an invalid board, however, you will not be disqualified for sending an invalid board to SimpletonUtils.verifyBoard. If you don't verify the board, a warning will be sent to console output if debug is on (edit SimpletonConfig.java).

Entry template

Here is an example entry to follow:

package SimpletonChess;
import SimpletonChess.SimpletonPlayer;
import SimpletonChess.SimpletonUtils;

public class MyEntry extends SimpletonPlayer {

    /**
     * Return the name of our bot to the controller
     */
    public String getName(){
        return "MyEntry";
    }

    /**
     * Method to carry out the logic for our entry
     */
    public void move(){
        SimpletonUtils utils = new SimpletonUtils();
        int[][] board = utils.read(); // Your own local copy of the board

        /*
        * TODO: Template. Add logic here
        */

       utils.submitBoard(board); // Note that you will be disqualified if your board is invalid! Check it with utils.verifyBoard(board), just use an if statement.
    }

}

** Remember to add your entry to the controller's main class, SimpletonTournament.java, when you're finished! **

Controller

The controller is on GitHub. (Link will be added when the controller is ready)

Your entries are expected to be written in Java (unless I find the time to write a console parser).

Final words

Good luck simpletons! I would very much like to see an entry using the monte carlo method, that would be splendid!

Also, a fantastic link for all things chess programming related: http://chessprogramming.wikispaces.com/

That's it from me, send your entries over today!

---

Notes

• I know there is another KOTH chess tournament. I don't think this is a duplicate since it has simpler rules and different pieces
• Is this too similar to checkers?

---

TODOs

• Fix overbolding

• Fix possibility to mess up the board with illegal moves (feedback needed)

• Themed intro, since a lot of other people are doing it (feedback needed!)

• Finish controller

• Add some diagrams

• Fix numerous typos and formatting errors

Answer 11

How Many Isomers of Nonane / Undecane Are There?

Background

Hydrogen and carbon form various series of compounds called hydrocarbons. Carbon forms four bonds and hydrogen forms 1 bond. The alkanes are the series of hydrocarbons without any double bonds between carbon atoms. The first four alkanes are shown below. Hydrogen atoms are omitted for simplicity. We know each carbon forms four bonds, so the unused bonds must have hydrogen atoms on them.

Methane     Ethane    Propane    n-Butane    Isobutane
C           C-C       C-C-C          C-C     C-C-C
                                       |       |
                                     C-C       C

Note that Methane, Ethane and Propane have only one isomer, whereas Butane comes in two isomeric forms. Both have four carbon atoms but in n-Butane they are arranged in a continuous chain, whereas in Isobutane (also known as 2-Methyl Propane) they are arranged as a continuous chain of 3 atoms plus a side branch of one carbon atom.

In both cases, the ten loose bonds on the carbon atoms are occupied by hydrogen atoms. In general, for hydrocarbons with no rings or multiple bonds, the formula is Cn H(2+2n).

Task

1. Your task is to create a program or function that accepts a single integer 0 < n < 10 and outputs to STDOUT or a file all the possible structural isomers of the hydrocarbon of formula Cn H(2+2n). That is to say, all the different ways in which n carbon atoms can be connected together, assuming freedom to twist about all bonds.

2. The carbon atoms shall be represented by the symbol C. In the interest of simplicity, hydrogen atoms shall be omitted. The bonds shall be represented by the symbols - and |. Only horizontal and vertical bonds are allowed. Each isomer shall be represented by a network of carbon atoms separated by bonds. As such the character C will appear on a grid of pitch 2x2.

3. Your program / function shall draw each possible isomer once and only once. The type of isomerism to be considered is structural isomerism. That is to say, compounds with different branching patterns shall be considered different. Different stereoisomers and different conformations shall be considered equivalent. Any conformation that complies with Rule 2 is valid.

4. The different isomers shall be displayed one below the other, in any order. To assist in checking, each isomer shall be preceded by a sequential number (starting at 1) on its own line. There shall be no more than 5 blank lines between any isomer and the preceding / following numbers. Unnecesary whitespace to the left and right of each isomer shall not exceed 10 characters in either direction.

5. To avoid extreme brute force solutions, execution time shall not exceed 1 minute on my machine for any input case.

6. Scoring: This code golf. Shortest code wins. If your program can handle up to n=11 instead of n=9 there is a -50% bonus. Above n=9 is significantly harder, because the sidechains can themselves have sidechains.

Above n=11 there exist some isomers that cannot be represented according to the rules of this question as some atoms would overlap.

The number of isomers for each value of n is given in https://oeis.org/A000602. Note that behaviour for n=0 can be undefined. The names of the isomers are here: http://www.kentchemistry.com/links/organic/isomersofalkanes.htm

n       0  1  2  3  4  5  6  7   8   9  10   11   
isomers 1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159

EXAMPLE OUTPUT n=6 (all 5 possible isomers) Note: you must display the isomers one below the other. They are displayed side by side here to save space. For further explanation, a video explaining structural isomerism with this example is here: https://www.youtube.com/watch?v=qOhEJK4Umds

1            2          3           4         5
                                                C
                                                |
C-C-C-C-C-C  C-C-C-C-C  C-C-C-C-C   C-C-C-C   C-C-C-C
               |            |         | |       |
               C            C         C C       C

EXAMPLE OUTPUT n=8 (only some of the possible isomers, you must display them all.)

n-Octane

C-C-C-C-C-C-C-C

3,4dimethyloctane. Those who know about stereoisomerism will know that in 3 dimensions the bonds are arranged in a tetrahedron around the carbon atom. This means that this compound can exist in 3 distinct forms: a lefthand form, a righthand form and a mirror symmetric form. For the purpose of this question these are equivalent and any one of the following is acceptable (and there are many other acceptable ways of drawing this isomer.)

    C-C-C-C          C          C-C-C-C             C          C-C-C-C       C-C-C-C-C-C  
      |              |              |               |            |               | |
  C-C-C-C      C-C-C-C-C-C        C-C-C-C       C-C-C-C-C-C    C-C-C-C           C C
                   |                                  |    
                   C                                  C

EXAMPLE OUTPUT n=10 (only some of the possible isomers, you must display them all.)

triisopropylmethane, or 2(methylethyl)1,3dimethylpentane (n=10 is the smallest n where there can be a sidechain of three C atoms, and therefore also the smallest n where a sidechain itself can be branched.)

    C   C
    |   |
  C-C-C-C-C
      |
    C-C-C

2,2,3,4,4pentamethylpentane (it can be shown that for n=10 a maximum of 2 carbon atoms can be completely surrounded by four other carbon atoms each.)

  C   C
  |   |
C-C-C-C-C
  | | |
  C C C

Answer 12

Solve the nonogram

fastest-codegame

Nonograms, also known as Hankie or Picross, are fascinating. They are really simple is essence, but to solve the most complexe one, some tricks have to be learned.

Basics

Nonograms are usually presented this way :

           1
         2 1 2
       3 2 1 2 3
     +-----------
    3|
  2 2|
1 1 1|
  2 2|
    3|

The numbers in lines and columns determine how much box in a row will be present, and how much sets there will be on this line/columns. The seconde line says 2 2which means "2 boxes in a row, at least one space, 2 boxes in a row" Let's give it a try with the 5x5 sample above. I will use #for boxes and .for blank confirmed.

           1
         2 1 2
       3 2 1 2 3
     +-----------
    3|
  2 2|
1 1 1|
  2 2|
    3|
As we said, second line says 2,some spaces,2. 
As we are playing on a 5x5 board, there's only one space remaining after 
putting the boxes, so their position is certain.
           1
         2 1 2
       3 2 1 2 3
     +-----------
    3|
  2 2| # # . # #
1 1 1|
  2 2|
    3|
There's some other 2 2 rows, let's fill them !

           1
         2 1 2
       3 2 1 2 3
     +-----------
    3|   #   #
  2 2| # # . # #
1 1 1|   .   .
  2 2| # # . # #
    3|   #   #

We can say this puzzle is over :
Look at the 1 1 1 rows, they have already 2 blank confirmed
which means there's only 3 spaces left. We can fill these, and complete the
puzzle.

           1
         2 1 2
       3 2 1 2 3
     +-----------
    3|   # # #
  2 2| # # . # #
1 1 1| # . # . #
  2 2| # # . # #
    3|   # # #

We didn't checked all confirmed blank, but it's not the matter, we only need
to check the boxes. Note that the 3 rows has been useless to solve this 
puzzle.

There you got the basics, but some tips on the wikipedia page could be useful.

Goal

Your job is to write a program in the language you want to solve nonograms.

There shouldn't be any problem, but here's some loopholes that are forbidden, just in case :).

I'd also like you to write which down command have to be run to execute your code, and

Input

The input can be graphic, an array, a string via stdin, or whatever you want. You may hard-code it, I want to know how fast your program is to solve nonograms, not how fast it is to parse datas. I'll provide two format for each test case. A ASCII-Art'd one, as shown above, and one structured as an array in the form :

 [[columns],[lines]]
 columns and line will also be noted the same way, the array for the sample :
 [[[3],[2,2],[1,1,1],[2,2],[3]],[[3],[2,2],[1,1,1],[2,2],[3]]]

Output

You must produce the solved nonogram, formated as you want as long as it is clear. It should be outputed via stdout, or your language closest alternative, as an Image, Ascii-art or left on top of the stack.

Test Cases

Puzzles will never be greater than 99*99, nor smaller than 2*2.They all are solvable by using basic techniques, the ones shown on wikipedia are far more than enough.

I might add some test cases latter, but big ones take time, a lot of time. If you want to give it a try, post one with your answer, and it will be added if it is solvable without any guess. Which means solving only those one won't be necessary nice, you need to be able to solve any "basic" nonogram : No multi-row - multi depth contradiction looking. Even contradiction shouldn't be necessary

5x5
[[[3],[2,2],[1,1,1],[2,2],[3]],[[3],[2,2],[1,1,1],[2,2],[3]]]

           1
         2 1 2
       3 2 1 2 3
     +-----------
    3|
  2 2|
1 1 1|
  2 2|
    3|

10x10

[[[3],[2,2],[1,1,1],[2,2],[3],[3,1],[2,7],[1,1,1,1],[2,2,2],[3,3]],[[3],[2,2],[1,1,1],[3,2,2],[2,2,3],[1,1,1,1],[2,4,1],[3,1,2],[4],[1]]]

                       1
             1         1 2
           2 1 2   3 2 1 2 3
         3 2 1 2 3 1 7 1 2 3
       +--------------------
      3|
    2 2|
  1 1 1|
  3 2 2|
  2 2 3|
1 1 1 1|
  2 4 1|
  3 1 2|
      4|
      1| 

30x30

[[[10,6,10],[9,8,9],[7,10,7],[7,14,6],[6,15,5],[6,15,5],[5,17,4],[5,19,4],[26,3],[4,2,10,2,3],[4,1,8,1,3],[3,12,3],[3,9,3],[3,16,3],[3,16,3][3,16,3][3,16,3][3,16,3],[3,9,3],[3,12,3],[3,1,8,1,3],[4,2,10,2,3],[4,25],[4,19,4],[5,17,5],[6,16,5],[6,12,7],[8,10,8],[8,8,10],[10,6,10]]

                                  4 4                   3 4
                                  2 1                   1 2
               10 9 7 7 6 6 5 5  10 8 3 3 3 3 3 3 3 3 3 810   4 5 6 6 8 810
                6 810141515171926 2 112 91616161616 912 1 2 41917161210 8 6
               10 9 7 6 5 5 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 325 4 5 5 7 81011 
              +------------------------------------------------------------
            30|
            30|
            30|
          11 9|
           9 6|
   6 3 1 1 3 5|
   4 3 1 1 3 3|
   2 3 2 2 4 3|
     2 6 5 4 1|
     1 6 5 5 1|
         7 5 6|
         9 7 8|
            30|
            30|
            30|
            30|
            30|
            30|
            28|
          26 1|
 1 7 1 5 1 6 2|
 2 6 1 3 1 4 2|
 2 5 1 3 1 4 3|
 3 3 1 1 1 3 4|
     4 3 1 3 4|
       6 3 3 6|
           8 8|
            30|
            30|
            30|

Solution

For those who are interested, here's the solution for the test cases.

 5x5

           1
         2 1 2
       3 2 1 2 3
     +----------
    3| . # # # .
  2 2| # # . # #
1 1 1| # . # . #
  2 2| # # . # #
    3| . # # # .

10x10
                       1
             1         1 2
           2 1 2   3 2 1 2 3
         3 2 1 2 3 1 7 1 2 3
       +--------------------
      3| . . . . . . # # # .
    2 2| . . . . . # # . # #
  1 1 1| . . . . . # . # . #
  3 2 2| . # # # . # # . # #
  2 2 3| # # . # # . # # # .
1 1 1 1| # . # . # . # . . .
  2 4 1| # # . # # # # . . #
  3 1 2| . # # # . # # . # #
      4| . . . . . . # # # #
      1| . . . . . . # . . .

30x30
Hope you'll like it, it took me a lot of time :)
                                  4 4                   3 4
                                  2 1                   1 2
               10 9 7 7 6 6 5 5  10 8 3 3 3 3 3 3 3 3 3 810   4 5 6 6 8 810
                6 810141515171926 2 112 91616161616 912 1 2 41917161210 8 6
               10 9 7 6 5 5 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 325 4 5 5 7 81011 
              +------------------------------------------------------------
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
          11 9| # # # # # # # # # # # . . . . . . . . . . # # # # # # # # #
           9 6| # # # # # # # # # . . . . . . . . . . . . . . . # # # # # #
   6 3 1 1 3 5| # # # # # # . . # # # . . # . . . # . . # # # . . # # # # #
   4 3 1 1 3 3| # # # # . . . # # # . . . # . . . # . . . # # # . . . # # #
   2 3 2 2 4 3| # # . . . . # # # . . . . # # . # # . . . . # # # # . # # #
     2 6 5 4 1| # # . # # # # # # . . . . # # # # # . . . . # # # # . . . #
     1 6 5 5 1| # . . # # # # # # . . . . # # # # # . . . . # # # # # . . #
         7 5 6| . . # # # # # # # . . . . # # # # # . . . . # # # # # # . .
         9 7 8| . # # # # # # # # # . . # # # # # # # . . # # # # # # # # .
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            28| . # # # # # # # # # # # # # # # # # # # # # # # # # # # # .
          26 1| . . # # # # # # # # # # # # # # # # # # # # # # # # # # . #
 1 7 1 5 1 6 2| # . . # # # # # # # . # . # # # # # . # . # # # # # # . # #
 2 6 1 3 1 4 2| # # . # # # # # # . . # . . # # # . . # . . # # # # . . # #
 2 5 1 3 1 4 3| # # . . # # # # # . . # . . # # # . . # . . # # # # . # # #
 3 3 1 1 1 3 4| # # # . . . # # # . . # . . . # . . . # . . # # # . # # # #
     4 3 1 3 4| # # # # . . . # # # . . . . . # . . . . . # # # . . # # # #
       6 3 3 6| # # # # # # . . # # # . . . . . . . . . # # # . # # # # # #
           8 8| # # # # # # # # . . . . . . . . . . . . . . # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
            30| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
60x60
Not completed, not tested

                              60| # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
                     6 3 1 1 335| # # # # # # . . # # # . . # . . . # . . # # # . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
             6 3 1 1 3 6 6 5 5 1| # # # # # # . . # # # . . # . . . # . . # # # . . # # # # # # . . # # # # # # . . . . # # # # # . . . . # # # # # . . #
                             647| . # # # # # # . . . . . . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
                   5 1 1 3 2 1 4| # # # # # . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . # . # # # . # # . # . . . . # # # #
                   1 2 1 2 2 1 4| . # . # # . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . # # . # # . # . . . . # # # #
                     1 2 1 2 1 3| # . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . # # . # . . . . . # # #
                       2 2 1 1 2| # # . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . # . . . . . . . . # #
                           3 2 2| # # # . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # #
                           3 2 1| # # # . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
                           3 3 1| . # # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
                             1 8| # . # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                         1 4 4 1| # . # # # # . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
                         1 3 2 2| # . # # # . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # #
                         1 3 2 1| # . . # # # . . . . # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
                         2 4 3 1| # # . # # # # . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # .
                         4 3 3 2| # # # # . # # # . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # #
                         3 4 3 1| . # # # . . # # # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
                           1 3 8| # . # # # . # # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                       1 3 1 5 1| # . # # # . # . # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
                         1 5 4 2| # . # # # # # . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # #
                       2 4 2 3 2| # # . # # # # . # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # .
                   2 2 2 1 3 2 1| # # . # # . # # . # . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . #
                   1 2 2 1 3 2 2| . # . # # . # # . # . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # #
                   3 1 2 2 4 2 2| # # # . # . # # . # # . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # .
                 3 1 2 4 3 2 2 1| # # # . # . # # . # # # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . #
               1 2 2 3 2 3 2 2 2| # . # # . # # . # # # . # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . # #
               1 2 2 3 2 3 2 2 2| # . # # . # # . # # # . # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . # # .
                 4 2 6 4 2 2 2 1| # # # # . # # . # # # # # # . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . # # . #
                   6 6 4 2 2 2 2| . # # # # # # . # # # # # # . # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # . # # . # # . # #
               3 3 2 3 5 3 2 2 2| # # # . # # # . # # . # # # . # # # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # . # # . # # . # #
             1 1 3 2 6 3 4 2 2 2| # . # . # # # . # # . # # # # # # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . # # # # . # # . # # . # #
         1 5 2 2 1 1 3 2 2 2 2 1| # . # # # # # . # # . # # . # . # . # # # . . . . . . . . . . . . . . . . . . . . . . . . . # # . . # # . # # . # # . #
         1 3 1 2 2 1 1 4 3 2 2 2| # . # # # . # . # # . # # . # . # . # # # # . . . . . . . . . . . . . . . . . . . . . . . # # # . . . # # . # # . # # .
           1 3 1 2 2 3 4 4 2 2 2| # . # # # . # . # # . # # . # # # . . # # # # . . . . . . . . . . . . . . . . . . . . . # # # # . . . . # # . # # . # #
       1 1 1 1 2 2 3 4 2 2 2 2 1| # . # . # . # . # # . # # . # # # . . # # # # . . . . . . . . . . . . . . . . . . . . # # . . # # . . . . # # . # # . #
             3 6 2 4 1 3 3 2 2 2| # # # . # # # # # # . # # . # # # # . # . # # # . . . . . . . . . . . . . . . . . . # # # . . . # # . . . . # # . # # .
           2 2 3 2 4 1 4 4 2 2 2| . # # . # # . # # # . # # . # # # # . # . # # # # . . . . . . . . . . . . . . . . # # # # . . . . # # . . . . # # . # #
       2 2 3 2 1 1 1 4 2 2 2 2 1| # # . . # # . # # # . # # . # . . # . # . # # # # . . . . . . . . . . . . . . . # # . . # # . . . . # # . . . . # # . #
         2 6 2 1 2 1 2 3 3 2 2 2| # # . . # # # # # # . # # . # . # # . # . # # . # # # . . . . . . . . . . . . # # # . . . # # . . . . # # . . . . # # .
           4 5 4 2 1 1 3 4 2 2 2| # # # # . # # # # # . # # # # . # # . # . # . . # # # . . . . . . . . . . . # # # # . . . . # # . . . . # # . . . . # #
         3 5 4 2 1 1 2 2 2 2 2 1| . # # # . # # # # # . # # # # . # # . # . # . . # # . . . . . . . . . . . # # . . # # . . . . # # . . . . # # . . . . #
           8 4 4 1 2 1 2 2 2 2 1| # # # # # # # # . # # # # . # # # # . # . # # . # . . . . . . . . . . . # # . . . . # # . . . . # # . . . . # # . . # .
         3 4 1 2 4 1 3 2 2 2 2 2| # # # . # # # # . # . # # . # # # # . # . # # # . . . . . . . . . . . # # . . . . . . # # . . . . # # . . . . # # . # #
           3 6 2 4 1 6 4 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # # # . . . . . # # # # . . . . . . . . # # . . . . # # . . . . # # . #
       3 6 2 4 1 4 2 2 2 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # . # # . . . # # . # # . . . . . . . . # # . . . . # # . . . . # # . #
       3 6 2 4 1 5 1 1 3 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # # . # . . . # . # # # . . . . . . . . # # . . . . # # . . . . # # . #
           3 6 2 4 1 212 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # . # # # # # # # # # # # # . . . . . . . . # # . . . . # # . . . . # # . #
       3 6 2 4 1 2 1 1 3 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # . # . . . . # . . . . # # # . . . . . . . # # . . . . # # . . . . # # . #
           3 6 2 4 1 4 1 4 2 2 4| # # # . # # # # # # . # # . # # # # . # . # # # # . . . . # . . . . # # # # . . . . . . # # . . . . # # . . . . # # # #
         3 6 2 4 1 4 1 2 2 2 2 4| # # # . # # # # # # . # # . # # # # . # . # # # # . . . . # . . . . # # . # # . . . . . # # . . . . # # . . . . # # # #
         3 6 2 4 1 4 1 2 2 2 2 3| # # # . # # # # # # . # # . # # # # . # . # # # # . . . . # . . . . # # . . # # . . . . # # . . . . # # . . . . # # # .
         3 6 2 4 1 4 1 2 2 2 2 4| # # # . # # # # # # . # # . # # # # . # . # # # # . . . . # . . . . # # . . . # # . . . # # . . . . # # . . . . # # # #
       3 6 2 4 1 4 1 2 2 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # . . . . # . . . . # # . . . # # . . . # # . . . . # # . . . . # # . #
       3 6 2 4 1 4 1 2 2 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # . . . . # . . . . # # . . . # # . . . # # . . . . # # . . . . # # . #
       3 6 2 4 1 4 3 2 2 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # . . . # # # . . . # # . . . # # . . . # # . . . . # # . . . . # # . #
   3 6 2 4 1 4 1 1 1 2 2 2 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # . . # . # . # . . # # . . . # # . . . # # . . . . # # . . . . # # . #
 3 6 2 4 1 4 2 1 2 2 2 2 1 2 2 1| # # # . # # # # # # . # # . # # # # . # . # # # # . # # . # . # # . # # . . . # # . . . # # . . # . # # . . . . # # . #
   3 6 2 4 1 4 2 1 2 2 2 2 1 2 4| # # # . # # # # # # . # # . # # # # . # . # # # # . # # . # . # # . # # . . . # # . . . # # . . # . # # . . . # # # # .
         3 6 2 4 1 4 2 1 6 4 412| # # # . # # # # # # . # # . # # # # . # . # # # # . # # . # . # # # # # # . # # # # . # # # # . # # # # # # # # # # # #

Winning criteria

Puzzle solving might be long, who will find the best heuristics? Who will find the best implementation? Fastest code will win (code will be running on my computer, i5-4440, and must not use more than 4GB of RAM). You'll be scored using the 60*60 nonogram sandbox note : have to be added. Other test cases are here to help you while developing your submission. If there's a need of a Tie-breaker, i'll provide more complex test case (maybe a 90*90?)

Sandbox

I have two questions for the sandbox :

• Do I need to put more explanations?

• Is there too much grammar/others faults? (I'm not native, sorry :()

As suggested by @steveverrill, I changed it to a fastest-code contest, some basic things changed. It makes much more sense, thanks.

I added the first part of the 60x60 nonogram, still have to form the array, and do the columns. I know it is ugly, but I wasn't able to come with a nice one which would be viable AND long to solve. T

Answer 13

4-Way Intersection Simulator

Consider an intersection as follows:

Cars will drive up any of the above Input lanes, and will exit out of any of the 3 other Output lanes. The goal is to take the list of cars, their arrival time, and their destination, and to return the times they will exit the intersection.

We will measure the time that it takes a car to cross an intersection as 1 Tick. We will assume that the time it takes for a car to approach and leave the intersection to be 0 ticks.

Each input acts as a queue of cars. Each tick, the car that has been at the front of its respective lane the longest will cross the intersection in his respective direction.

Priority

If multiple cars have been waiting for the same amount of time, the rightmost car has priority. If there are 2 cars that are on opposing sides, they will both cross at the same time (as described below), unless only one of them is turning left. If that is the case, the car not turning left will have priority. Two cars may turn left at the same time. If there are 4 cars that arrive at the same time, the car in Input 1 will have priority.

After the car to cross has been chosen, other cars may cross at the same time, assuming their paths don't cross. Priority is given to the lane directly across from the crossing car, then to the car to right, then to the car to his left.

Input/Output

Input will be a list of cars. Each car will be passed as a tuple containing the cars' unique ID, arrival time, arrival lane, and destination lane. The arrival lane will never be the destination lane.

Your program should output a list of cars, where each car is a tuple containing the cars' unique ID and the time it reaches its destination.

I don't care if the input format exactly matches the examples below. What I do care is that you input a list of tuples/lists and output a list of tuples/lists.

Examples

[(0, 5, 2, 3)] -> [(0, 6)] 
Car 0 arrives in lane 2 at tick 5.  He leaves in lane 3 at tick 6

[(0, 3, 1, 3), (1, 3, 3, 1)] -> [(0, 4), (1, 4)] 
Car 0 and 1 arrive in lanes 1 and 3 at tick 3.  They both leave at tick 4.

[(0, 0, 3, 1), (1, 0, 4, 2), (2, 1, 4, 2)] -> [(0, 2), (1, 1), (2, 3)]
Car 0 and 1 arrive in lanes 3 and 4.  Their paths intersect, so car 1 leaves first 
because it is the rightmost car.  The next tick, car 2 arrives, but car 0 has been 
waiting the longest, so car 0 leaves next.  Finally, car 2 leaves at time 3.

[(0, 0, 1, 2), (1, 0, 2, 3), (2, 0, 3, 4), (3, 0, 4, 2)] -> [(0, 1), (1, 3), (2, 1), (3, 2)]
All four cars arrive at the same time.  Car 0 has the priority as it is in Input 1.  
Car 2 is directly across from it, and both are turning left, so they cross at the same 
time.  Car 1 is turning left, so car 3 will cross next, followed by Car 1.

[(0, 0, 1, 4), (1, 0, 2, 1), (2, 0, 3, 2), (3, 0, 4, 3)] -> [(0, 1), (1, 1), (2, 1), (3, 1)]
All four cars arrive at the same time, all are turning right, so all leave at tick 1.

[(0, 0, 1, 3), (1, 0, 4, 2), (2, 0, 3, 2), (3, 1, 1, 4), (4, 1, 4, 1), (5, 1, 2, 1), (6, 2, 3, 4), (7, 2, 1, 3), (8, 3, 1, 4), (9, 3, 4, 2), (10, 3, 3, 2)] -> [(0, 1), (2, 1), (1, 2), (3, 2), (5, 2), (6, 3), (4, 4), (10, 4), (7, 5), (9, 6), (8, 6)]
Car 2 is the rightmost, and has priority.  Car 0 is also able to cross at Tick 0
Car 1 has now been waiting the longest, and has priority.  Both Car 3 and 5 are able to
cross as well.  Car 4 was waiting behind Car 1, and so Cars 4, 6, and 7 arrive at the
same time.  Car 6 is the rightmost, so he exits at tick 3 while cars 8-10 arrive.
Car 4 is the next rightmost, so he makes his turn next, while Car 10 makes his right turn.
Car 7 finally has his turn, and crosses.  Car 8 is behind Car 7, and Car 9 intersects with
Car 7, so neither cross at the same time, but both are able to cross the next tick.

Answer 14

Black and White Morphing

popularity-contest graphical-output

Given two black and white images, the goal is creating a animated black and white gif that transforms one image into the other and back.

The catch is, that for all frames the number of black pixels (as well as the number of white pixels, obviously) stays the same. You can assume that the two input images have the exact same size and the exact same number of black pixels.

Discussion

@PeterTaylor suggested making the restrictions that from one frame to the next you can only swap adjecent pixels. Otherwise this challenge would be almost the same as this one, so we need a further restriction.

My goal is enforcing a 'slow' transition that can produce nice effects. One way of picturing that was considering the white pixels as fluid or sand that has to be rearranged step by step into the other image.

@trichoplax suggested making the limit that e.g. only 5% of the pixels may change in each transition.

Test Cases

This is a first series of test cases, all 320x386px and 33844 white pixels.

Answer 15

Find the maximum of ax+b

Find the maximum of ax+b online

You are given a list of (a,b), and a list of x. Compute the maximum ax+b for each x. You can assume a, b and x are non-negative integers.

But this time, items in the list are added dynamically. Your program should support the following operations (you can rename the operations if that's convenient):

• Add a,b, to insert (a,b) into the list.
• Query x, to find the maximum ax+b in the current list, with the given x.

Your program or function must run in expected (to the randomness if your code involves that, not the input) O(nlogn) time where n is the total input length (or total number of operations).

You can write a complete program, a function, a list of functions or methods doing each operation, or a function taking one operation each time. For the later two cases, you can either return or print the result after each operation, or add an "output" operation, or output automatically when the program ends.

Examples

(will be added later.)

This is code-golf. Shortest code wins.

Note about the complexity:

If you used a builtin having a good average-case complexity, and it can be randomized to get the expected complexity easily in theory, you can assume your language did that.

That means, if your program can be tested to be O(nlogn) (in theory), with edge cases for your code, but not the implementation of your language, we'll say it is O(nlogn).

Answer 16

Half-finished Idea:

Diffusion Battle

king-of-the-hill

---

Overview

Players are all present on a toroidal grid. Each player has 16 particles to start with. The total number of particles is fixed but they can change colour. Each turn a player decides what type of action to take for each particle of their colour, but cannot control the direction, which is always random.

All players' particles then move in a random direction at the same time, possibly resulting in some of them changing colour. The player with the most particles of their colour at the end of the game is the winner.

---

Action types

A player chooses from the following actions for each particle:

• Drift: do not attempt to change the colour of other particles
• Eat: attempt to change the colour of other particles

Each of these actions is applied after all players' particles have aimed in a random direction. This may result in two particles aiming for the same cell. No cell will end up with more than one particle, but aiming for the same cell results in interaction, with no movement and the following rules being applied:

• If both particles chose Drift, nothing happens.
• If both particles chose Eat, nothing happens.
• If one particle chose Eat, the particle that chose Drift will become the colour of the particle that chose Eat.

Clearly choosing Eat is always an advantage when two particles aim for the same destination. However, if a particle aims for a cell that no other particle is aiming for, it will move there, with the following rules being applied:

• If the particle chose Drift it will move with no change.
• If the particle chose Eat it will move and take on a random colour (which may be its own colour or that of any other player).

N particles colliding

The case where N particles are all aiming for the same destination cell is a generalisation of the case for 2 particles. None of them will move to the destination cell and the following rules will be applied:

• If all of the N particles chose Drift, nothing happens.
• If all of the N particles chose Eat, nothing happens.
• If some chose Drift and some chose Eat, none will move and all those that chose Drift will change to a colour chosen randomly from those exhibited by those that chose Eat. If there is more than one particle of a given colour that chose Eat, that colour will have a correspondingly higher probability of being chosen.

When N = 2 this reduces to the case described for 2 particles.

It follows that if the N particles are of the same colour, then regardless of their individual choices none will move and they will all remain the same colour.

Collision with a particle that was unable to move

What happens to particles that were aiming for an empty cell but the cell is not empty because its occupant was unable to move?

---

Sandbox thoughts

EITHER

• ALL THOSE THAT AIMED FOR THE SAME CELL AFFECT EACH OTHER

OR

• THOSE THAT AIMED FOR THE SAME CELL DO NOT MOVE, ALL THOSE THAT END UP ADJACENT AFFECT EACH OTHER

I favour the second but I need to consider how it would work with large numbers of particles adjacent.

• Zgarb pointed out in chat that it would be better to have a small probability of changing if failing to eat, so that the penalty for failure is not so extreme. I'm likely to use this as it is fine tunable.

Answer 17

Minimum? Vertex Cover

code-challengeoptimization

<insert definition of (minimum) vertex cover here>

Given a graph, you must output a valid vertex covering of that graph. The entry with the smallest total size (number of vertices) over five test cases (TBD) wins.

Input

Your program will be run with one argument given: a file name. For example:

python findacover.py graph_1.txt

Submissions will read the graph from the file specified. The format of the file will be:

5
0:1 2 3
1:0 3
2:0
3:0 1 4
4:3

The first line is simply the number of vertices in the graph (V). The next V lines are the list of vertices. Each line consists of the vertex number and a colon, followed by a space-separated list of vertices connected to that vertex by an edge.

Note that each edge will be listed twice, once for each vertex it connects. You can see in the example that the edge connecting 1 and 3 is present on the line for both vertices.

Output

Output is simply a list of vertices that represent a valid vertex covering of the input graph. Output should be written to STDOUT (so my validator can score it.

I will strip all non-digit, non-space characters ([^0-9 ]) from your output and interpret the remainder as a space-separated list. For example, outputs [0, 1, 2, 3] and 0 1 2 3 will be treated the same.

For the example graph above:

Valid:

0 1 2 3 4

or

0 3

among others.

Invalid:

0 1 2

This does not cover the graph, since the edge between 3 and 4 is not covered.

Rules

• Submissions will be run once for each graph.
• You have a time limit of five minutes for each graph. You cannot "roll over" unused time to the next graph. This time is clocked on my computer, an i7-3770K CPU with 16GB RAM, running Ubuntu 14.04. If you might bump against this limit, make sure you send a "best-yet" output before time is up.
• Feel free to use multiple threads, but keep it on the CPU. My graphics card is not your playground.
• Your submission must be deterministic. If you use a PRNG, seed it with a constant value.
• You cannot use any built-in or third-party function designed to solve vertex covering problems.
• Standard loopholes apply. This means (for example) that you cannot hardcode your submission to these test cases. If I choose five more test cases to run, you should get comparable (obviously not exact) results.

Scoring

Your score is the number of vertices in your cover. If you return anything except a valid covering, or do not return anything within the time allotted, your score for the graph will be 200000.

Score is summed over five test cases, each consisting of a graph with 20k to 100k vertices. The lowest total score wins.

<link to test cases here>
<insert generator/validator/scorekeeper here>

---

Sandbox

• Does the "function designed to solve vertex covering problems" need to be better specified? If so, how could I word that?
• Are the graph sizes and time limits reasonable? They are designed to prevent a straight brute-force attack, but I don't believe they are too large to prevent a good approximation. Are they too small?

Answer 18

Be the shortest in your own standard

This was cops-and-robbers at the beginning. But I'm thinking of changing it to a user scored challenge instead, where each user can propose a limit number of regex, and for each regex, the shortest matched program gets one point.

Working in progress. More details to be added

---

Task

(To be added.)

How to answer

In each answer, you should write a program with length n for the above task, and optionally a regex with no more than n/2 bytes.

The regex should consist of only character literals (including escaped ones) and [...] (...) ? * + |. You cannot use other features such as specifying number of repetitions or the beginning/ending anchors.

If you choose to include a regex, you should also specify whether programs should be nearly-matched or nearly-unmatched by the regex, defined as following:

• A regex nearly-matches a program, if there is a character C and a subset S of the set of all occurences of C in the program, that when everything in S is replaced by a character C', the program will be matched by the regex.
• A regex nearly-unmatches a program, if for every character C and every subset S of all occurences of C in the program, that when everything in S is replaced by a character C', the program will not be matched by the regex.

If you choose to nearly-match, it must nearly-match your own program in the same answer. And this program must be shorter than any other answer nearly-matched by the regex. The same applies if you choose to nearly-unmatch, where your program must be shorter than anything nearly-unmatched.

The programs and regexes should only use printable ASCII, tabs and newlines.

Each user can write any number of programs, but can write at most 5 regexes at the beginning. You can write one extra regex for each 5 upvotes you get.

Scoring

For each regex, if one of your program is the first of the shortest of the programs nearly-matched/unmatched by the regex according to the specification, you get 2 points. If the regex is not your own, you get one extra point.

Each of your program can be scored more than one times if they are the shortest for more than one regex.

You should not post an answer that doesn't get any score at the time you post it. But you can leave it there if it loses all the score it had. And you can post an answer that is only the shortest for your own regex.

Rules about posting and editing answers

You can always edit regexes into an answer, if you are allowed to write more regex. But once a program is the shortest for a regex at the time you post the regex, you can't post another regex that makes this version of the program shortest.

You should not edit a program in a way that it loses scores from some regex. And if you edit, you should keep the version that is paired with a regex in your answer.

Regexes should not be modified after posting for any reason if they are valid.

You should not post programs/regexes that is the same as a previous submission.

Answer 19

Inspired by the last question asking for the masses of the elements, this challenge will be slightly more specific. In this challenge, you will find the molar mass of a sequence of amino acid peptides.

Amino acids, of which there are 21, are the units that combine into chains and then bend and change shape to form proteins, which serve widely varying functions in cells and in the body of most all living organisms. Scientists working with peptides, such as chemists and doctors, can easily synthesize a desired peptide chain in the lab thanks to the powers of modern technology. After some purifying and such, he will have the desired sequence in the form of a white powder/crystal like substance.

However, this is science! This means that he will eventually need to weigh out a desired amount of his sequence to perform some reactions or tests. To do this, he needs to know its molar mass.

Today, we know that there are 21 amino acids, and we have found their molar masses and given them names and symbols, just like the 118 elements on the periodic table. They are as follows:

Name           Symbol   Molar Mass
Alanine         A        89 
Cysteine        C        121
Aspartic acid   D        133
Glutamic acid   E        147
Phenylalanine   F        165
Glycine         G        75 
Histidine       H        155
Isoleucine      I        131
Lysine          K        146
Leucine         L        131
Methionine      M        149
Asparagine      N        132
Proline         P        115
Glutamine       Q        146
Arginine        R        174
Serine          S        105
Threonine       T        119
Selenocysteine  U        169
Valine          V        117
Tryptophan      W        204
Tyrosine        Y        181

BUT WAIT!! (how do I make this text bigger?)

But wait!!

But wait!!

But wait!!

Unlike the elements, the mass of a peptide sequence isn't just the sum of the masses of the constituent amino acids! Amino acids combine in a reaction called a hydrolysis reaction that forms a bond called a peptide bond. Take a look at this diagram:

A hydrolysis reaction is a reaction in which two large molecules combine to make a larger one, but in the process lose a small molecule. In this case, they lose a water molecule (hence the name hydrolysis). Since the mass of water is 18, when two peptides bond together in a chain they lose 18 molar mass units. So if our sequence was AC (Alanine-Cysteine), the mass would be 89 + 121 - 18 = 192.

The Challenge

Your job is to golf a program that computes the molar mass of a given peptide sequence. The sequence will be specified by their one letter symbols, in all caps.

Examples: A returns 89

AC returns 192

WAGAKRLVLRRE returns 1453

Shortest byte count wins, no loopholes. Weights must be hardcoded in the program somehow.

Answer 20

Fundamentals of City Planning

In this challenge, you are a city planner. You have been given an N by M rectangle to fill with residential lots of size K and roads of width 1. You know that money is made based on the number of residents in the city, so your goal is to maximize the number of lots in your rectangle. However, the following rules are enforced:

• Roads have a width of 1 square, and all roads must be orthogonally connected to each other.
• Every lot must share at least 1 side with a road
• Lots must all be the same size K. They can be in the shape of any polyomino of size K.
• There must be at least 1 road that touches the edge of the rectangle, as your residents need to be able to get in and out!

The winner of the challenge is the one that:

1. Fits the most lots across all of the below examples. In the case of a tie:
2. Fastest solution, unless multiple answers are running under a second. In that case:
3. The earliest posted solution

Submitted answers must run in under a minute.

STDIO

You will be passed three integers, N, M, K. You need to output the generated grid. Roads should be represented by .. Lots should be ordered and numbered, and when printed should be represented by their number mod 10. The ordering can be arbitrary, and is simply used to distinguish lots on output. Empty squares are allowed and are represented by #.

Test Cases for correctness

Provided solutions can be numbered differently, rotated, and/or reflected

1 2 1 
.1

1 3 1
1.2

2 2 1
1.
2.

3 3 1
123
...
456

3 3 2
11#      11.      #11     
2..  or  2..  or  2..
233      233      233

Test cases used for scoring:

20 15 1
20 15 2
20 15 3
20 15 4
20 15 5
20 15 6
20 15 7
20 15 8

Answer 21

Catch the robber

king-of-the-hill grid java

This is my first time making a KOTH. I (mostly) will not post this KoTH. Read the ReadMe file for more info.

---

Overview

A cop spots a robber and the robber runs and ends up in a basement. The cop then goes into the basement and locks the door.

Gameplay

The basement consist of 49 rooms with dimensions 7 x 7. The top-left room has coordinates [0,0] while the bottom-right room has coordinates [6,6]. The cop starts on the room with coordinates [6,3] while the robber starts on the room with coordinates [0,3].

Cop

The cop moves first. The cop can move in one of these directions:

• Up
• Right
• Down
• Left
• Here

The direction here indicates that the cop will stay in the current room and will not move. The rest of the directions are self-explanatory. The cop can move in a particular direction if it is a valid one, i.e, the cop cannot move out of the grid or move into a room with a trap.

The cop can also put traps in a room. At the start of every match, the cop has 3 traps. Once a trap has been placed, the cop will not be able to move into the room where the trap is placed.

The cop also has 3 pressure sensors at the start of every match. The cop can move into a room where a pressure sensor has been placed.

If the robber moves into an adjacent room of the cop, the cop will be alerted.

Robber

The robber can move in the same directions as the cop does. The robber too cannot move outside the grid.

The robber has two TrapDetector5000 which can be used by the robber. It will detect if there is a trap in one of the adjacent rooms that the robber is in.

If the cop moves into an adjacent room of the robber, the robber will be alerted.

Goal

The cop must catch the robber as soon as possible. This can be done by moving into a room where the robber is. The cop will also catch the robber if the robber moves into the room where the cop is.

If the robber moves into a room where the cop has placed a trap or a pressure sensor, the cop will be alerted and the robber will not be able to move for 2 turns, if the room had a trap. However, the robber will be able to move if the room had a pressure sensor.

The robber will be alerted if the robber steps into a room with a pressure sensor.

Controller

The controller is written in java and can be found here. As a cop or a robber you each have to each complete implement a Java class.

You have to implement the Cop interface if you are writing a Cop Bot and implement the Robber interface if you are writing a Robber Bot.

There is an enum direction with 5 directions Here, Up, Right, Down, Left which you can use when building your Bot.

You can use the Grid.isValidMove(direction) to check if that direction is a valid move. This is for Cops.

You can use the Grid.isValidPosition(direction) to check if that direction is a valid move. This is for Robbers.

You also may write additional functions within that class. The controller comes with one working example of a simple cop and robber bot.

Please use java 7 and please do not exploit stuff in the controller and cheat.

Note that your bot needs to return an int from takeTurn within 200 milliseconds. Failure to do so will result in the disqualification of your Bot.

Scoring

Each cop plays 10 rounds against each robber and the number of moves each robber makes in each round will be added up and this is the score of that particular robber. The same goes for cops.

The robber with the highest score and the cop with the lowest score wins!

Answer 22

Blackjack

How to Play

Blackjack is for any number of people, but there will be only one in this case. The goal is to get as close to 21 as possible without going over. Aces will be 1 for this program. All other face cards are worth 10.

To start, the player is dealt two cards. They can then choose to hit (take another card) or stand. This repeats until they go over 21 (bust) or decide to stay.

If the player busts, their score is 0. Otherwise, their score is the total of all the cards.

Input/Output

1. The program should output 2 "cards" (randomly choose between 2, 3, 4, 5, 6, 7, 8, 9, 10, K, Q, J, and A).
2. The player then inputs a move, stand or hit.
3. If he/she stands, output Final Score: [total of cards].
4. If he/she hits, output another "card". Output Bust! if the score is over 21.
5. Repeat steps 2-4 until the player busts or stands.

Test Cases

Output: 5 K
Input:  hit
Output: 6
Input:  stand
Output: Final Score: 21



Output: A Q
Input:  hit
Output: 7
Input:  hit
Output: 6
Output: Bust!

Rules and Other Notes

• Aces are always 1.
• Each output/input should be on a new line.
• Any trailing spaces and newlines are okay.
• Assume that all input will be valid. You don't need to notify the player of invalid input.
• You cannot read from a file or other source.

Scoring & Submissions

• This is code golf. Shortest code in characters wins.
• How to win: post the shortest working code within one week.
• Please include the language, number of characters, and code. Explanations are appreciated, but not required.

Good luck!

Tags

code-golf, game, card-games

Sandbox Questions

Anything I'm forgetting? Does anything need more clarification?

Answer 23

roll me back a game of hearts

code-golf card-games

Roll me back a game of hearts
given just a deck of cards
please.

So, I've been playing a game of hearts (https://en.wikipedia.org/wiki/Hearts) with three of my friends but I'm not entirely sure if all of them were playing perfectly according to the rules. So I'd like to replay the game with everyone's cards openly visible. And because you like algorithms, you offered me your help determining everyone's cards from the final deck after each hand. However, I can't quite remember if you promised me a full program or just a named function.

A card is represented with two characters. The first character represents its value and is one of 23456789TJQKA (2-10, jack, queen, king, ace). The second character represents its suit and is one of CDHS (clubs, diamonds, heards, spades).

The input is a list of 52 cards. It can either be a list (array, vector...) of two-character strings or a single space-separated string. You will be given the cards in the exact order they were played. The list represents a valid deck and 2C is the first card in the deck.

Output four sets of cards, each representing the starting hand of one player. The first set may correspond to any player but the rest must be ordered in the order of play (so if the first hand to be output is the third one to play, the rest must be in the order of fourth, first, second). The cards in each player's hand may be output in any order (it's a set). If you choose to output a single string, separate the cards in each hand with spaces and the hands with newlines.

Game rules:

Rules irrelevant to this challenge have been formatted in small font

• There are variants for three to six players but the base variant is for four players so let's assume this one.
• ^{Before the main game each player passes three cards to another player. Since this is a lossy operation, let's just ask for the hands after this passing moment.}
• Each game consists of 13 tricks. Each trick consists of each player in clockwise order playing one card from their hand, then one player "taking" the trick.
• The first trick starts by the two of club. Each subsequent trick is started by whichever player took the previous trick.
• ^{The first player in a trick can play any card. The first player cannot play hearts unless hearts have already been played in that game or he has no other cards, however. The other players have to play the same suit as the leading player if they have that suit, otherwise they can play any card. Scoring cards cannot be played in the first trick}
• The player that played the highest valued card of the same suit as the leading card of that trick takes that trick. E.G.: in 2C AD KC 5C, the king of clubs takes the first trick. In 2H KS AS QS the leading player takes the trick (and fourteen points).
• ^{The objective of the game is to end up with the fewest points possible. A player gets one point per each hearts taken, and 13 poins for the queen of spades.}

You may assume that the deck of cards is valid (exactly one of each card) and that the two of clubs has been lead. You may also assume that the rules concerning the order of play and trick taking have been followed. You may not assume the rules concerning which cards can be played when have been followed. Heck, you don't even know that I haven't been cheating. Because a player may have been dealt nothing but hearts, you may not even assume only non-scoring cards have been played in the first trick (if everyone on the planet plays 100 games in their life, this may realistically happen to someone).

---

Should I loosen the I/O requirements? How much?
Formatting advice? Which parts (if any) should I trim down? What needs to be clarified?
Anything else?

Answer 24

How to Create a Dating Website

Dating websites make lots of money. You want lots of money, so you're going to make a dating website. However, we all know that the most important part of any dating website is the algorithm, so you need to build that first.

When your customers will sign up, they are going to fill out a short survey describing themselves*. On the survey, they filled out personal interests, personality traits, and other important data for you to process using your algorithm.

Your algorithm must then accept two things:

1. A list of people, where each person has a list of traits
2. A list of trait pairs (A, B), where each pair has a score S. A trait pair matches a couple if one of them has trait A, and the other has trait B. The score can be negative. If A and B are different, and both people have both of the traits, then the score is doubled.

Your algorithm must then output a list of couples. Each person must be included in a couple exactly once, and only two people is allowed in each couple**. Your score is the sum of each couple's score. A couple's score is the sum of each of the trait pairs they match.

Input/Output

Input is given as shown in the following example. Ignore the # comments

4         # Number of customers
1,3,5,7   # Customer 1's list of traits
1,2,4,5,6 # Customer 2's list of traits
1,6,7     # Customer 3's list of traits
1,2       # Customer 4's list of traits
4         # Number of trait pairs
1,2,-2    # Trait 1 and 2 give a score of -2
1,6,4     # Trait 1 and 6 give a score of 4
2,3,-4    # Trait 2 and 3 give a score of -4
6,6,5     # Trait 6 and 6 give a score of 5

Let's say you output:

2,3 1,4

Then that would match Customer 2 to 3 and 1 to 4.

If we look at 2,3, they match:

• The first trait pair, because Customer 3 has Trait 1, and Customer 2 has Trait 2
• The second trait pair, because they both have Traits 1 and 6. (This means double the score)
• The fourth trait pair, because they both have trait 6. However, because the trait pair only references 1 trait, we don't double the score.

Adding it all up, we get -2 + 4*2 + 5 = 11. The other couple scores -2 + -4 = -6, so the final score is 11 + -6 = 5.

The person who generates the highest scoring pairing wins the challenge. In the case of a tie, the program that generates it the fastest wins. If programs are generating the answer in under a second, then the earliest posted answer wins.

Question: I'm planning on doing 10K people, 500 traits, an average of 50 traits per person, and 5K trait pairs. I'm doing large numbers because I want efficient algorithms, but I want to know if the numbers are feasible

_{*They clicked a check box saying that they didn't lie, so we know that the survey is accurate}

_{**You can assume everybody is a hermaphrodite}

Answer 25

LindenMASM

LindenMASM is an Assembly-like programming language which can be used to generate images from Lindenmayer systems. Lindenmayer systems are very interesting in the fact that they can provide a rudimentary method of generating fractals, such as a Sierpinski triangle. They are also interestingly able to mimic nature very closely for some reason, which can be seen in the below image. You will be implementing a LindenMASM interpreter in a language of your choice.

Understanding Lindenmayer Systems

You should check out the Wikipedia page for a more detailed overview of Lindenmayer systems, as I will simply describe the process of actually using a system. I will be referring to a turtle in this explanation. A turtle is simply the device by which an L-system is drawn. We will use a dragon curve L-system as an example.

Firstly, we need to consider the variables we will be using. In the case of an L-system, a variable is used to control evolution, and does not actually correspond to any movement. We will need two for this, so let's call X and Y our variables.

Next, we would define our constants. In most L-Systems, the character F refers to moving forward, - turns left and + turns right. We will follow these conventions here, and specify that - turns the turtle 90 degrees left and + turns the pointer 90 degrees right.

After this, the axiom needs to be defined. This is the starting point of the system, i.e. what it looks like after 0 iterations. In our case, we will set it to FX.

Finally, we need to define some rules. Rules are applied by going through each character of the axiom, and if one of them matches a rule, replace it with the defined set of instructions. Our rules are that X -> X+YF+ and Y -> -FX-Y. I will show a quick evolution of steps, so you can see how these rules are applied.

• n=0 - FX
• n=1 - FX+YF+
• n=2 - FX+YF++-FX-YF+
• n=3 - FX+YF++-FX-YF++-FX+YF+--FX-YF+
• n=4 - FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+

When this is interpreted, however, since X and Y don't control movement, the interpreted steps for n=4 would look like this:

F+F++-F-F++-F+F+--F-F++-F+F++-F-F+--F+F+--F-F+

Simplified..

F+F+F-F+F+F-F-F+F+F+F-F-F+F-F-F+

Which would result in the following drawing:

Syntax

There are only a few keywords available in LindenMASM which you will need to implement.

1. STT - Begins every LindenMASM file.
2. AXI $ - Sets the axiom (initial state) of the system.
   • $ is a series of commands/variables/constants, ranging from the built-ins plus any user-defined functions.
3. DEG $ - Sets the degree of which all turns will follow.
   • $ will be a integer or float between 0 and 359, inclusive. The default value is 90 otherwise.
4. MOV $ - Sets the move distance of which all position adjustments will follow.
   • $ will be a integer or float between 1 and 100, inclusive. The default value is 10 otherwise.
5. INC $ - Sets the number of iterations the generation should go through.
   • $ will be a number between 0 and 30, inclusive. The default value is 0 otherwise. (a value of 0 means just the axiom is displayed).
6. SET $ # - Sets a constant $ to a specified command #
   • $ will be a letter between A and Z, inclusive, and will be uppercase.
   • # will either be a 0 or a 1, where a 0 corresponds to the constant being one that draws forward, and a 1 corresponds to the constant being one that moves fowards.
7. RPL $ # - On every iteration, variable/constant $ will be replaced with the command/variable/constant string #.
   • $ will be a letter between A and Z, inclusive, and uppercase. It does not need to be SET to be replaced.
   • # is a string of commands/variables/constants that $ should be replaced with.
8. END - Ends every LindenMASM file.

Each keyword should be placed on a new line. Your program should fail parsing if (a) The file does not start with STT or does not end with END. Your program should assume that the rest of the keywords will have proper arguments attached to them.

Below is a list of all of the regular commands that cannot be defined by the user:

1. + - Rotates the pointer to the right DEG degrees.
2. - - Rotates the pointer to the left DEG degrees.
3. [ - Saves the pointer's coordinates and heading to a list.
4. ] - Pops the last value of a list and sets the pointer's coordinates and heading to that.

Examples

I will give 5 examples, each of which will have detailed information on the pattern, plus a link to have it visualized online.

Fractal Tree - n=6, axiom=X, Θ=25, X->F-[[X]+X]+F[+FX]-X, F->FF (Test Online)

STT
AXI X
DEG 25
MOV 10
INC 6
SET F 0
RPL X F-[[X]+X]+F[+FX]-X
RPL F FF
END

Gosper Curve - n=4, axiom=F, Θ=60, F->F+G++G-F--FF-G+, G->-F+GG++G+F--F-G (Test Online)

STT
AXI F
DEG 60
INC 4
SET F 0
SET G 0
RPL F F+G++G-F--FF-G+
RPL G -F+GG++G+F--F-G
END

Koch Variant - n=4, axiom=F-F-F-F, Θ=90, F->FF-F--F-F (Test Online)

STT
INC 4
RPL F FF-F--F-F
SET F 0
AXI F-F-F-F
END

Sierpinski Triangle - n=7, axiom=F-G-G, Θ=120, F->F-G+F+G-F, G->GG (Test Online)

STT
RPL G GG
RPL F F-G+F+G-F
DEG 120
AXI F-G-G
SET F 0
SET G 0
INC 7
END

Dragon Curve - n=12, axiom=FX, =90, X->X+YF+, Y->-FX-Y (Test Online)

STT
INC 12
DEG 90
AXI FX
SET F 0
RPL X X+YF+
RPL Y -FX-Y
END

Input

Aside from the examples given above, your code should support the following test cases as well:

Input:

SET F 0
AXI FF
RPL F F-F+F
END

Output: Error: No STT at beginning.

Input:

STT
SET F 0
AXI FF
RPL F F-F+F

Output: Error: No END at ending.

Output

Your program should output the resulting image by outputting an image or by drawing to the screen (e.x. turtle graphics). If you would like to check out a Python 3 example, here is a Github link to pylasma.

---

This is code-golf, so least number of bytes wins.

Answer 26

Print time of day using words

I'm not sure if this has been done before. I thought it must have but I could not find one using search. The idea is basically, given a number in seconds, e.g. the output from time(NULL). Return the current time in words using 12 hour clock, e.g.

HALF PAST FIVE PM
A QUARTER TO SIX PM
TEN TO SIX PM
SIX O'CLOCK PM
SIX TEN PM
TWELVE NOON
TWELVE O ONE AM

Has this challenge been done before?

One thing I cannot decide is when the "PAST" should be used. Should it be used only when there is less than 15 minutes left? Should it be FIVE FIFTY FIVE or FIVE TO SIX?

Answer 27

Maze to regex

Suppose we have an ASCII maze like so:

#######
#s# # #
# # # #
#     #
# ### #
# #  e#
#######

The input maze will have the following properties:

• One cell (marked s) will denote the start of the maze, and a separate cell (marked e) will denote the exit.

• The walls will be denoted by hashes #, and empty corridors will be denoted by spaces.

• The maze will be a perfect rectangle, have no cycles, and will consist of exactly one connected component (i.e. all cells will be reachable)

A single character from NSEW represents a move North, South, East or West respectively, and consists of moving two characters in the specified direction. For instance, the above example is a 3 by 3 maze where the following cells can be occupied:

#######
#x#x#x#
# # # #
#x x x#
# ### #
#x#x x#
#######

A string consisting of NSEW is said to solve a maze if applying each move in turn results in the exit being reached at some point in time, regardless of whether the string continues on afterward. If a move is blocked by a wall, the move is ignored and no movement occurs.

Example strings which solve the above maze are SEES, SENSES and SSSSSNENNNNNSENNNNNSSSSSSSSWW.

The challenge

Your task is to write a program or function which takes in an ASCII maze and outputs a regex. The regex must match a string of NSEW if and only if it solves the given input maze.

For instance, all solutions to the 2 by 2 maze

#####
#s#e#
# # #
#   #
#####

can be encapsulated by the regex

^(([NEW]|S[WS]*N)*S[WS]*E([ES]|W[WS]*E)*W[WS]*N)*([NEW]|S[WS]*N)*S[WS]*E([ES]|W[WS]*E)*N[NEWS]*$

(Try it online at Regex101)

Available features

You may only use the following regular expression features:

^$         Start and end anchors respectively
N|E        Alternation
NE         Concatenation
()         Grouping
*          Repetition (0+ times)
+          Repetition (1+ times)
?          Optional (0 or 1 times)
[NESW]     Character classes (but not negated classes)

In particular, recursion, wildcards, lookaheads and other unlisted features are not allowed.

---

Sandbox questions:

• What would be better, metagolf (scoring by providing a few test mazes, and taking the sum of output regex lengths) or code-golf (any output regex is okay as long as it is finite and correct)?

• I've chosen this ASCII representation because it looks the nicest, but I'm not sure if it's the most convenient. I'm open to suggestions for alternatives.

• What is the best way to test submissions? I can write a bunch of test cases per maze, but it's impossible for me to test an infinite number of strings.

Answer 28

Be Rational! Finding Rational Roots of Polynomials

---

In this challenge you are to find all rational zeroes of a polynomial. The results have to be exact. I would suggest using The Rational Root Theorem.

Input

---

Input can be through function argument, command argument, or user input. Input will be a polynomial. The polynomial may have rational coefficients. If a term has a coefficient of zero, that term will not be included in the input. x^1 will be abbreviated as x.

Examples:

-x^7+4x^4/7-21x^2/2+5x+23/19
...//More to be added when posted

Output

---

Output will be a list of the rational roots of the input polynomial. Output can be through function return value or stdout. If output in string format, you will use improper fractions separated by commas. The output must be simplified as much as possible. Duplicate roots should not be printed more than once.

Examples:

4/5,2/3,-15/2
...//More to be added when posted.

---

Example Cases

> x^2-1
1,-1
...//More to be added when posted.

Just like all codegolf questions, the answer with the lowest byte count wins.

Questions:

Is this too much like Peter's earlier question?
Are there any points I haven't covered or are not clear?
Any grammar/spelling mistakes?
Any tips on improved formatting?

Answer 29

Rec(ursion)less execution

We have a simple (non-Turing complete) language.

Each line of program is a set of terms separated by single space. Some of terms (ending with ()) are function calls. Some lines (whose first term ends with :) are function definitions. The lines that are not function definitions are called expressions.

This is a sample program:

funa: one two three
funb: funa() four oclock rock
here we go funb()

Here we have two function definition lines and one expression line.

And this is BNF for this language just for clarity:

literal ::= [any printable char other than ' ', ':', '(', ')']+
function_header ::= literal ':'
function_call ::= literal '()'
term ::= literal | function_call
expression ::= term | expression_list ' ' term
function_definition ::= function_header expression

program_line ::= function_definition | expression
program ::= [program_line '\n']+

The task is to write a program or function that validates the program P and performs EXECUTE(P) if the program adheres to validation rules.

Validation rules:

1. EXECUTE(P) eventually stops (it's not Turing complete - enough to check if one of the called functions would eventually cause itself to be called - either being recursive itself or "mutually recursive" with other function it calls),

2. while calling EXECUTE(P) -> EXECUTE_LINE(P,L), each function definition search succeedes (in other words - the program will not try to call undefined function).

If program does not pass validation rule 1 or 2, ERROR: RECURSIVE FUNCTION or ERROR: UNRECOGNIZED FUNCTION should be printed respectively.

When both rules seem to be violated, assume that search for undefined function causes the algorithm to fail (stop) instantly, so recursion that would occur later if the function was found, is not reported. We only report ERROR: UNRECOGNIZED FUNCTION in this case (see Example 5 below).

In similar way, if recursion prevents a call to function that would not be found otherwise, even though the function containing call to unrecognized function is called only ERROR: RECURSIVE FUNCTION is reported (see Example 4 below).

If validation does not report any of those two errors, EXECUTE(p) should be called.

Executing a program is defined like this:

EXECUTE(P)
  - for each line L in the program P:
     - if L is not a function definition EXECUTE_LINE(P,L)

EXECUTE_LINE(P,L)
  - for each term T in L:
      - if T is a literal
          print T followed by single space
        else
          FH = T without '()' + ':'
          FDL = find in P a line starting with term FH
          FD = all terms of FDL after FH
          EXECUTE_LINE(FD)
          

Example 1:

a: b()
b: a()
c: cucumber
other: nofun()
d: apple banana and c()
we have d()

Output:

we have apple banana and cucumber

Note, that in spite of existence of mutually recursive function definitions a and b and function definition other calling undefined function nofun error was not raised, because execution never goes to any to this functions.

Example 2:

other: nofun()
c: apple banana and cucumber
we have other()

Output:

ERROR: UNRECOGNIZED FUNCTION

Example 3:

a: b()
b: a()
c: apple banana and cucumber
we have b()

Output:

ERROR: RECURSIVE FUNCTION

Example 4:

a(): a() nofun()
hello a()

Output:

ERROR: RECURSIVE FUNCTION

We don't output ERROR: UNRECOGNIZED FUNCTION, because the program would never try to execute nofun, recurring infinitely into first term of definition of a.

Example 5.

a(): nofun() a()
hello a()

Output:

ERROR: UNRECOGNIZED FUNCTION

We don't output ERROR: RECURSIVE FUNCTION here, because the program would fail to find definition for nofun before even tring to recurse into a.

Accepted solution: a function or a program that takes a program in the above-defined language, validates and runs it. You can assume that program has already been split into single lines, however you can use raw input or accept program as single string when convenient.

This is code-golf, so the shortest submission in term of bytes will win. However, all working submissions in all languages will be appreciated.

Answer 30

Triple Triad Tournament! king-of-the-hill

---

(anything in italic parenthesis is a note for the sandbox)

About Triple Triad

Triple Triad is a card game from the Final Fantasy series. I've never played a FF game that included it, though, so I'm only familiar with the version in the Pokémon fangame Pokémon Insurgence. It may or may not be different than the original version, so apologies in advance if this isn't quite what you're expecting. :)

In Triple Triad, each card has 4 numerical stats that range from 1 to 10*: An "up" value, a "left" value, a "right" value, and a "down" value. Here's an example of a card with an "up" value of 1, a "left" value of 6, a "right" value of 3 and a "down" value of 2:

Triple Triad Rules

At the beginning of each game, players construct a "deck" of five cards, chosen from their entire collection. These cards are kept secret from the other player.

Triple Triad is played on a 3x3 grid. Players take turns choosing a card from their deck and placing it on an empty square of the grid. The goal of the game is to control the majority of the cards when the grid is filled. When the game is complete, one card is randomly selected from the loser's deck and given to the winner.

Control

When a card is placed on the grid, it is controlled by its owner. In order to come out of the game victorious, you must gain control of cards that the opponent played.

To gain control of an opponent's card, you must place a card of your own that "beats" it adjacent (not including diagonals) to the card you want to take control of. Whether or not your card beats the opponent's depends on their stats and which side you place your card on.

Imagine this board as the current game state and the blue card as a card in my deck:

If I want to take control of the opponent's Numel, I have to place my Mareep adjacent to it. This leaves only two options: The top middle square or the middle right square. If I were to place it on the top middle square, my card would be to the left of the opponent's. As a result, Mareep's "right" value of 2 would be contested against Numel's "left" value of 4. 2 is not greater than 4, so my opponent would retain control of Numel. Note that my value must be strictly greater; a tie would be the same as a loss.

If I were to place my card in the middle right corner, it would be below the opponent's card. As a result, Mareep's "up" value of 4 would be contested against Numel's "down" value of 3. 4 is greater than 3, so I would gain control of Numel (which would turn blue to indicate that).

This process is applied in all four directions at once. If there was a card below Mareep with an "up" value of 1 or 2, I would gain control of it as well. However, gaining control is not done passively or recursively. Control can only be contested at the exact moment a card is placed, and gaining control of a card does not count as "placing it".

Tournament Rules

Each bot is given a budget of (TBD) with which to purchase cards before the tournament (this will be done by the author, not the bot itself, and will be hardcoded into the bot). Here are the cards, along with their costs:

There - 1000
 will - 1500
   be - 1500
    a - 2500
 list - 3000
 here - 4000

The bots will play in a Round Robin tournament with Bo3 matches (subject to change. not sure if round robin will work well or if i should be using Bo5 or what). The bot that wins the most matches will be declared the winner.

Match Procedure

1. Each bot chooses 5 cards from their collection to create a deck. (If they have less than five cards, they forfeit the match.)
2. The game is played as described above, until the board is filled. (i'm not sure how to decide who should go first. alternate? winner of the last game? loser?)
3. When the game is complete, a random card from the loser's deck is removed from their collection and inserted into the winner's collection. (At the end of the match, each bot's collection is reset to its original state.) (i'm not totally sure about choosing a random card. it's how the original game works, but it's not necessarily 100% fair. the idea is that over the course of a round robin tournament, any RNG variance will be smoothed out, but i don't know...)
4. Repeat steps 1 through 3 until one bot has won 2 games.

Input / Output Specifications and Controller Details

(none yet lmao)

---

^{* The Insurgence variant has some nonsense regarding Pokémon types at higher difficulty levels, but this challenge will ignore that.}