490
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

| |
\$\endgroup\$

2956 Answers 2956

1
26 27
28
29 30
99
1
\$\begingroup\$

Find longest alphabet path (code-golf)

You are given a 2d array of size nxn that is filled with lowercasel letters a-z. Your goal is to find the longest continous path by only moving up/down/left/right. A path is a sequence of cells of the 2d grid, where the successor of the current cell must be a neighbour that is above, below, left or right. Also, each cell of the array can only be visited once per sequence. The value (the lowercase letter) of the successor must right before or after the one in the current cell (if the current cell has the value c, the successor must have value b or d).

Output

You have to solve two tasks:

  • The challenge stated above
  • The challenge stated above plus another restriction: successors can only have the next letter in the alphabet, but not the previosu (if the current cell has the value c the successor must have the value d)

The output must consist of two n x n grids the same size as the input, each for one of the two tasks. The grids have to be the identical again, but all the unused cells that are not part of the longest sequence have to be set to a whitespace. If there are two or more longest sequences, only one arbitrary one of them has to be in the output.

Testcases (more to be added)

Input:  Out1:  Out2:     
ababa   ababa  ab         
babab   babab        
ababa   ababa        
babab   babab        
ababa   ababa

Input:  Out:  Out:
aba     aba   ab
aba
aba

abcd  abcd  abcd
hgfe  hgfe  hgfe
gfeb  gfeb  
babc  babc
| |
\$\endgroup\$
  • \$\begingroup\$ This looks to me like a duplicate of codegolf.stackexchange.com/q/44922/194 \$\endgroup\$ – Peter Taylor Jan 28 '15 at 10:53
  • \$\begingroup\$ Thanks, I didn't remember that challenge, but to me it seems different enough for a new challenge: On the one hand this challenge uses a 2d string instead of 1d on the other hand there is no restriction to words plus another output format needed. I think the overall ideas and needed approaches are quite different. Inspiration (i do not know what those puzzles are called genearlly) \$\endgroup\$ – flawr Jan 28 '15 at 10:59
  • 1
    \$\begingroup\$ I see it as two versions of the longest path problem on sparse graphs with different graphs. \$\endgroup\$ – Peter Taylor Jan 28 '15 at 11:06
  • \$\begingroup\$ Ok if you look at it like this, they are indeed the same problem, but I think the implementation will provide very different challenges. \$\endgroup\$ – flawr Jan 28 '15 at 11:14
1
\$\begingroup\$

Logic Dots - Posted

| |
\$\endgroup\$
  • \$\begingroup\$ This wants the tag puzzle-solver. It isn't clear until really late that the shapes to place are all lines (or a by 1 rectangles, if you prefer): making that clear quite early would be useful. Without that context, the two 2s in the second example look like a requirement to place a 2x2 square. On my first read-through I took "they can also be vertical" to mean that some of the input shapes could be vertical: it wasn't until I saw the examples that I could reinterpret it as "You may rotate the shapes when placing them". \$\endgroup\$ – Peter Taylor Jan 27 '15 at 9:30
  • \$\begingroup\$ @PeterTaylor fixed. \$\endgroup\$ – globby Jan 27 '15 at 15:48
  • \$\begingroup\$ Posting test cases as an answer is a bad idea. To shorten the post, you could try putting the examples side by side, and you could use Stack Snippets. \$\endgroup\$ – Peter Taylor Jan 27 '15 at 22:45
1
\$\begingroup\$

Hide your code in a Boggle board!

This proposal is intended to supersede my earlier proposal Find the Needle in the Haystack, of which I'm not convinced any more that it would work very well. I'll keep both proposals around for now, though.

The Cops' Challenge

First, choose a program output, consisting of less than 100 printable ASCII characters (character code 0x20 to 0x7E, inclusive) - in particular the program must be written on a single line.
Next, you should write a number of programs (not necessarily in the same language), which all output that exact same string (including any trailing newlines) to STDOUT or closest alternative. Each of those programs should be made up of less than 100 printable ASCII characters, too.
Finally, design a Boggle board, which contains all of these programs. The Boggle board may contain as many unused character as you wish, but it has to be rectangular and all characters have to be in the printable ASCII range. See "Boggle Rules" below for how the Boggle board works.

You want the number of programs to be large, the board to be small and the programs to be hard to find.

None of the programs must take any input. You may print to STDOUT, a GUI dialog (as with JavaScript's alert()), or assume a REPL environment (like a browser console) - but if it's different from STDOUT, you need to state clearly where your output will go in each case.

Each program has to complete within 5 seconds on a reasonable machine. You are not allowed to use cryptographic methods, hashing functions, random seeds or string compression.

If your submission's boggle board is X characters wide, and Y characters tall, and you've hidden N programs in it, your submission's score is N3/(X*Y).

You should deliver:

  • X, Y, N and your score.
  • The languages of your N programs, including output destination if it differs from STDOUT.
  • The Boggle board.
  • The output of the programs.

An answer is cracked if N programs in the specified languages are found by a single robber (see The Robbers' Challenge below). If your answer has not been cracked for 7 days, you may claim immunity by revealing the programs in your answer (to prove that your answer was solvable).

The winner will be the immune submission with the highest score.

The Robbers' Challenge

Every user has one attempt at cracking each submission. Your cracking attempt will be a list of programs found in a the submission's Boggle board. If your guess matches the description (all programs can be found according to the Boggle rules, all produce the correct output to the correct destination, and they are written in the required languages), and you are the first correct guess, then you get N*X*Y points. It is important to note that your programs do not have to exactly match the originals, as long as they meet the specification and can be found in the Boggle board. This means there could be more than one correct answer.

The robber with the most points wins. In the case of a tie, the robber who submitted fewer cracks wins.

Robbers should post their cracks as answers to the associated Robbers' thread.

Boggle Rules

  • To find a program in a Boggle board, you start at an arbitrary cell and add characters to the string by repeatedly moving to one of its neighbours.
  • You may move one cell at a time, horizontally, vertically, or diagonally.
  • No cell must be used more than once (within a single program or by multiple programs).

Example

Consider this Boggle board as a cop submission:

1$int
arun"
!pts0
b "2K

Along with the specification that the output is 20, and that there are 2 CJam programs, one Python 2 program and one Ruby program. A robber could now find:

  • K in the bottom right corner and 20 next to it as two valid CJam program.
  • print "20" as a valid Python 2 program:

    __i__
    _r_n"
    _pt_0
    _ "2_
    
  • puts"20" as a valid Ruby program:

    _____
    __u_"
    _pts0
    __"2_
    

If no one cracked this, the cop's score would be 42/(5*4) = 0.8. If someone did crack this, that robber would get 4*5*4 = 80 points.

Sandbox Notes

  • I intend to provide stack snippets which generate leaderboards for the cops and robbers.
  • The scores probably need some balancing. Suggestions?
  • I admit that the robbers' challenge is pretty similar to Calvin's Hobbies' recent challenge. This happened purely by accident - I was originally thinking about a word search C'n'R, which would have been too easily brute-forcible, so I changed it to a Boggle board. Of course, that doesn't matter when considering if it's a duplicate of course, but I think with hand-designed boards, looking for programs with fixed outputs in prescribed languages, makes this quite different and should hopefully make for a more balanced challenge. Furthermore, the cops' challenge of designing the boards is completely different. Please let me know if you disagree, though.
  • Should I allow cells to be reused within a single program?
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd guess that allowing cells to be reused within a single program would make it much harder for a cop to prevent multiple unintended programs appearing in the board. \$\endgroup\$ – trichoplax Jan 24 '15 at 10:10
  • 1
    \$\begingroup\$ I dislike the 'output any 100 printable ASCII characters rule' from the Unscramble challenge. It makes it too easy for cops, who can print out any stream of gibberish. It some languages, it is even possible for them to enter random characters without even knowing what the code does. \$\endgroup\$ – feersum Jan 26 '15 at 9:09
  • \$\begingroup\$ @feersum I'm absolutely open to suggestions for better tasks. \$\endgroup\$ – Martin Ender Jan 26 '15 at 10:18
  • \$\begingroup\$ How about recommend allowing cells to be reused (the whole fun of Boggle), but allowing one program per language? \$\endgroup\$ – Ypnypn Jan 29 '15 at 15:56
  • \$\begingroup\$ @Ypnypn hm, sounds like a good idea. \$\endgroup\$ – Martin Ender Jan 29 '15 at 18:44
1
\$\begingroup\$

Cursor Wars

This question is based off of my previous Navigate Text with Arrow Keys golf. Here, a segment of text is the battle arena, and the opponents move like cursors.

Idea 1: Tron / Light-Bikes

As the cursors move left to right, they paint parts of the text. Neither cursor can move through a painted area. The cursor who runs out of moves first loses.

To add a twist to the board's topology, I could make it so that the text area is flipped for the opponent. If I see the board:

X-----
---
------Y

Then the opponent sees the board:

Y------
---
-----X

With line-wrapping working differently for each player, they don't have the same movement patterns.

Idea 2: Area Painting

Like in the Tron idea, cursors paint an area. The cursor that paints the most area wins.

I could make it make a few versions

  • Area painted once cannot be repainted: the winner is the cursor that painted the majority of area
  • Area can painted my moving right and cleared by moving left (backspacing). The winner is the one that painted the most area times time. (Each time step, players earn one point per painted area.)
| |
\$\endgroup\$
  • \$\begingroup\$ Idea 3 (rather vague): Put actual characters on the board and have people collect them to form words or sentences (either as the winning criterion or to get some form of power-ups). This could still be based around a Tron idea, or characters could simply be used up (so that others can still travel there, but thy can't collect those characters again). \$\endgroup\$ – Martin Ender Feb 9 '15 at 16:37
1
\$\begingroup\$

War of the Partitions

You have been assigned 1000 men to your cause, and you must fight your opponent on 20 different battlefields simultaneously. You must decide how to split up your 1000 men into 20 ways. Furthermore, since the Nth battlefield is larger than the (N+1)th battlefield, the 20 partitions must be in non-increasing order.

Each battlefield will have a skirmish. If you send more men than your opponent, you win that skirmish. Winning more skirmishes than your opponent across all battlefields scores you 1 Battle Point.

You will then face every other opponent, where you will be allowed to reassign your men to another location. You have a large supply of necromancers that allow you to keep all of your men alive from battle to battle, so you may allocate all 1000 men every time you face another opponent.

You will face each opponent 25 times. The player with the most Battle Points wins.

IO

You will be passed a string of the history of the battles between you and your current opponent. Each line consists of a different battle. The choices will be space separated, and your opponent's choices will be listed first, separated by a comma. The following input:

50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50,60 59 58 57 56 55 54 53 52 51 49 48 47 46 45 44 43 42 41 40
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50,51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 21

would represent two battles between a player. The first one would be a tie (each player won 10 skirmishes), while the second you won a Battle Point by winning 19 skirmishes.

You must return a string containing a space separated list of integers. The total of all of the values must be 1000, and must be in decreasing order.

| |
\$\endgroup\$
  • \$\begingroup\$ This game idea sounds very... familiar... but I don't see any KOTH based on it. Seems like a good idea. \$\endgroup\$ – PhiNotPi Feb 11 '15 at 23:38
  • \$\begingroup\$ Maybe change decreasing to non-increasing to prevent ambiguity. \$\endgroup\$ – randomra Feb 14 '15 at 17:43
  • \$\begingroup\$ Will the 25 battles be consecutive? It could be much quicker to save state (if allowed) than re-parse the whole history. (edit: file IO maybe slower, depends on the submissions and time limits) \$\endgroup\$ – randomra Feb 14 '15 at 17:49
  • \$\begingroup\$ @rcrmn the two battling bots are side by side. The top line is the first battle, the second line is the second battle. \$\endgroup\$ – Nathan Merrill Feb 24 '15 at 14:24
  • \$\begingroup\$ Sorry, I totally misread it! \$\endgroup\$ – rorlork Feb 24 '15 at 14:24
1
\$\begingroup\$

Code File Header

Do you have a large number of source files that you forgot to put a header on, but never bothered. Well then this challenge is for you! This is code golf, so shortest program that works wins.

The Challenge

Write a function (if your language doesn't support this, write a program, that accepts a cmd line arg for the file name) that takes the name of a file then attaches to the top of that file a comments section stating the name of the author, the current date, and the file name, as comments in your language (if your language supports comments, if not then in C-Style/Doxygen).

For instance, if your language was C/C++ the following must be appended at the top. using myself as the example.

/** \author Henry Schmale
 * \date 2015-02-19
 * \file [File Name]
 */

Notes

  • You may subtract the length of your name from your submission.
  • Languages that don't support file I/O are not eligible for this code golf.
  • The date code should be in a human readable format, no unix time. Preferably in ISO format.
  • if your language supports multiple comment formats, you may use either or so long as the final result is the same, a documentation header on that file.
| |
\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner I did this before I learned how to use doxygen. \$\endgroup\$ – HSchmale Feb 19 '15 at 0:47
  • \$\begingroup\$ What file name should be used if reading from stdin and writing to stdout? \$\endgroup\$ – Peter Taylor Feb 19 '15 at 12:21
  • \$\begingroup\$ The spec regarding the file name is a bit confusing now. First you say "Write a function [...] that takes the name of a file then attaches to the top of that file [...] the file name" but then you say "Assume the file name is main.c". I think a simpler option would be to always take the file name as a command-line or function argument, but allow people to choose between STDIN/STDOUT, file I/O and another function parameter/return value for the actual file contents. \$\endgroup\$ – Martin Ender Feb 20 '15 at 9:26
  • \$\begingroup\$ So why did you go back to disallowing languages without file system support now? :/ \$\endgroup\$ – Martin Ender Feb 21 '15 at 10:18
1
\$\begingroup\$

I'm only posting this in the sandbox because it may be too broad, even for a pop-con. If it gets some support I'll post it very soon.

Generating Postmodernist Writing and Other Logorrhea

Postmodernist writings are known for dealing with highly abstract ideas, potentially in a verbose manner that may sound nonsensical to someone reading them. This type of writing is often called logorrhea, and is not limited to postmodernism.

People have made programs that use natural language processing to generate realistic looking academic writings that are actually utter nonsense. One example is the Postmodernism Generator (wiki), which creates a random postmodernist essay every time the page is loaded. Another example is SCIgen (wiki), which can generate random papers about computer science.

Your task in this popularity contest is to write a program that can generate random, convincing paragraphs of academic logorrhea. You can choose what topic your program will generate text about. Postmodernism, CS, math, physics, and philosophy seem to be likely choices, but you can choose something else.

  • Your program must be able to take in a 32 bit integer (a value from 0 to 232-1) as a seed value and output a random paragraph of text on your topic. None of the 232 outputs should be identical. (If desired, you can include an option for no input, where the seed number is just chosen randomly.)
  • The paragraphs should be from 2 to 8 sentences long and between 300 and 1000 characters. The sentences should start with capitals and end with periods. Including other punctuation is optional.
  • The actual content of the sentences does not need to make grammatical sense, though it should consist of real English words. Presumably, the more it does make sense the more it will be upvoted.
  • You do not need to include author names or citations like the Postmodernism Generator does. You could though, and you are welcome to take some liberties and generate a full essay or a mini-paper or something if it's clear that what you're doing is more difficult that just generating a paragraph.
  • You may use any NLP libraries or resources, provided they don't already automatically generate random academic text. e.g. taking a paragraph from a random SCIgen paper would not be allowed at all.

The highest voted answer wins.

| |
\$\endgroup\$
  • \$\begingroup\$ Perhaps it needs to be narrowed down to a specific topic/area. How about homeopathy? \$\endgroup\$ – trichoplax Feb 25 '15 at 12:53
  • \$\begingroup\$ @trichoplax: Randomly generated articles on homeopathy might end up getting published. ;) \$\endgroup\$ – Alex A. Apr 2 '15 at 2:57
  • \$\begingroup\$ @AlexA. that would be priceless :) The winning condition could be the number of homeopathy journals it gets published in. \$\endgroup\$ – trichoplax Apr 7 '15 at 21:28
1
\$\begingroup\$

Which Children Don't Play Well Together? [code-golfchallenge]

You are a kindergarten teacher who is having problems with fights breaking out among the students. You have noticed that altercations happen only when certain groups of children are together. A group of children who can't play well together, but will coexist peacefully if any one student is removed from the group, is known as a MIKG (minimal incompatible kindergartener group). Every MIKG contains at least two children. To help prevent problems, you decide to identify all such groups of kindergarteners.

Each day, your class has Group Reading Time. This involves dividing the children into groups of 1 or more students, who take turns reading pages from a picture book. If all the children from an MIKG are placed in the same reading group, a commotion will erupt. The distraction rapidly involves all the students in the class, so you can't tell which reading group it originated from.

You want to find all the MIKGs as soon as possible, so you write a computer program to help you do the math. Let f(N) be the maximum number of days it will take to identify all the MIKGs in a class of size N, assuming an optimal strategy is used. The program should not take more than f(N) days to find the answer.

Input/Output

At the beginning of the program, it takes a positive integer input of N which tells the number of students in the class. Then, the program creates a plan for the day's reading groups. The user (kindergarten teacher) will input 1 if a disruption occurred during reading time, or a 0 if it remained calm. When the program determines all the MIKGs, it shall print them out and exit.

Challenge

You will be given random test cases for class sizes between (a) and (b). The goal is to determine the MIKGs in as few days as possible. The program that makes the smallest amount of queries is the winner, with tiebreak by earliest post.

Restrictions

  • The program must respond in under (x) seconds
  • Due to the interactivity requirement, you must submit a full program, not a function.
  • You may specify any format for the I/O as long as it is clear, unambiguous, consistent, and doesn't use characters other than printable ASCII and newlines.

Sandbox notes

| |
\$\endgroup\$
  • \$\begingroup\$ I presume that an MIKG must contain at least two children, but it would be good to make that explicit. \$\endgroup\$ – Peter Taylor Mar 12 '15 at 9:01
1
\$\begingroup\$

Musical Blinkenlights


Introduction

If you take a look at the front panel of your desktop or laptop computer, chances are that you'll find a handful of blinkenlights, including a hard disk activity indicator.

HDD blinkenlight turning on and off Image taken from here

The idea of this challenge is to "play" the Shave and a Haircut melody with that light.

The Task

Your task is to write a full program with the following behavior. If the program is placed in an empty directory, compiled (if applicable) and run, it causes the hard drive activity light to blink the notes of the Shave and a Haircut melody (unless, of course, the hard drive is active for some other reason). After that, it shall exit gracefully.

Precise Rules

The specification of the melody is as follows. Let t be a unit of time between 0.2 seconds and 0.7 seconds. Starting from some time tinit, the activity light shall blink at tinit, tinit + t, tinit + 1.5*t, tinit + 2*t, tinit + 3*t, tinit + 5*t, and tinit + 6*t. The blink must be long enough to be noticed by the human eye, but no more than 0.25*t.

Your program may create and modify any files and subdirectories in the directory it is placed in, including its own source code. The program does not have to be cross-platform, but you must state your operating system in your answer, and any necessary hardware requirements. In particular, some environments allow the blinkenlights to be controlled manually; this is perfectly acceptable, but must be explicitly stated.

Your program may not damage or significantly alter the host computer.

Scoring

This is code-golf, so the lowest byte count wins. Standard loopholes are disallowed.


Sandbox Notes

My main concern is whether my challenge would be too similar to this.

| |
\$\endgroup\$
  • \$\begingroup\$ This seems somewhat hard to test. The hard drive activity in response to a given file access sequence could depend on the model of drive, the filesystem, and any number of filesystem or OS config options. I don't think it's reasonable to expect anyone to be able to state the hardware and config requirements. \$\endgroup\$ – Peter Taylor Mar 16 '15 at 14:48
  • \$\begingroup\$ Musical nitpick: what you want is the Shave and a Haircut rhythm not melody. I thought you were asking something more difficult (especially as I didn't know that jingle was called that.) I like the challenge though. \$\endgroup\$ – Level River St Mar 24 '15 at 2:02
  • \$\begingroup\$ I think this might have a problem - lots of processes go on at all times in a computer. It would be hard to predict when the light just blinks randomly, and you couldn't shut those processes down (i.e, compiz on Linux). Plus, how would the challenge be verified, and what if it was only qualified/disqualified because of a random blink? \$\endgroup\$ – ASCIIThenANSI Apr 7 '15 at 13:07
1
\$\begingroup\$

I've been reading this forum for a bit and I thought it might be a good idea to do a short sequence of challenges themed on famous mathematicians. It's my first post here so please point out any shortcomings.

It is Irving Kaplansky's birthday today. Among other things he is famous for his conjectures on group rings. It is one of these conjectures in mathematics that requires virtually no special knowledge to understand. There a couple of words that need explaining in them but their definitions are very simple. These words are "group", "torsion-free group", "ring", "domain", "group ring", "idempotent", "unit".

Please read up if you want to. This challenge doesn't require understanding these words or the conjecture. All that's needed is the concept of a finite cyclic group. I'm sure most of you know what it is, but I'll give a short introduction. A cyclic group of order n can be understood as what you get when you take something (whatever) called a generator, say p, and decide that it can be raised to integer powers. These powers can be multiplied like so: pk * pl = pk+l. But there's one catch: whenever the exponents of the powers give the same remainder from the division by n, these powers are considered equal. This means, in particular, that there are exactly n powers really: p0, p1,...,pn-1. Any other power is equal to one of these.

The challenge is to implement a certain operation on certain formal expressions involving these powers. The expressions are of this form:

r0 * p0 + r1 * p1 + ... + rn-1 * pn-1,

where all ri are real numbers.

The operation, called multiplication, consists in, first, multplying two such expressions as if they were real sums, that is for example, for n=3:

(2 * p0 + 3 * p1 + 2 * p2) * (0 * p0 + 1 * p1 + 2 * p2)=

(2 * p0) * (0 * p0) + (2 * p0) * (1 * p1) + (2 * p0) * (2 * p2) +

(3 * p1) * (0 * p0) + (3 * p1) * (1 * p1) + (3 * p1) + (2 * p2) +

(2 * p2) * (0 * p0) + (2 * p2) * (1 * p1) + (2 * p2) + (2 * p2).

Then, we simplify each of the summands according to the rule

(r * pk) * (s * pl) = (r * s) * (pk * pl) = (r * s) * pk+l.

And finally, we simplify the resulting sum according to the rule

(r * pk) + (s * pk) = (r + s) * pk.

This means that for n=3, we have 2 * p2 + 5 * p5 = 7 * p2 because p2=p5!

The resulting sum is again of the form

r0 * p0+ r1 * p1 + ... + rn-1 * pn-1

after we order the summands by the exponents.

This operation is exactly the product in the group ring R[C], where R is the field of real numbers and C is a finite cyclic group. This group ring doesn't satisfy the hypothesis of Kaplansky's conjecture because finite cyclic groups aren't torsion-free.

Your task is to implement this in any language. Your program/procedure/whatever has to take a natural number n>0 as user input. This will be the order of your cyclic group. Then it has to take 2n "real numbers" as user input. I don't really care what the "real numbers" are in your implementation. They could be ints for all I care. Just make them something that can reasonably be interpreted as real numbers and has a reasonable arithmetic. The first n numbers will be the coefficients of the first formal sum and the other n numbers will be the coefficients of the second formal sum. You need to output the n coefficients of their product. You don't need to compute the product in the way describe above. It just has to be correct (modulo rounding errors and other things computers do wrong with numbers).

Shortest code wins. You can assume the input is valid. Both input and output can be in any reasonable form. I'm not sure if this is a good restriction on this site, but I'd like you to think "actually usable". Though I don't really care about how long it takes to compute. I guess all standard loopholes apply, as I've noticed it seems to be a mantra here. :-)

As I said, please help me improve this challenge and oh, feel free to edit.

| |
\$\endgroup\$
  • \$\begingroup\$ Did you mean to shift the indices in "r_1 * p^0 + r_2 * p^1 + ... + r_(n-1) * p^(n-1)"? Also, do I understand right that you're asking for us to multiply formal polynomials under the relationx^n = 1? \$\endgroup\$ – xnor Mar 22 '15 at 22:53
  • \$\begingroup\$ @xnor I didn't mean to do that! And yes, that's one way of saying this. Another way of saying it is to multiply elements of the group ring R[C] where C is a finite cyclic group and R is the field of real numbers. My goal is to introduce the concept of a group ring and this is one of the simplest cases. For the infinite cyclic group it would amount to the Laurent polynomials, and that's too familiar I think. This is the next simplest case. \$\endgroup\$ – ymar Mar 22 '15 at 22:59
  • \$\begingroup\$ @Martin Done, thanks! \$\endgroup\$ – ymar Mar 22 '15 at 23:18
  • \$\begingroup\$ @xnor I've corrected the indices (there were some more errors). Do you think this is too simple? I was thinking of doing it with the quaternion group... \$\endgroup\$ – ymar Mar 22 '15 at 23:19
  • \$\begingroup\$ Added the statement that this is a group ring product. \$\endgroup\$ – ymar Mar 22 '15 at 23:23
  • \$\begingroup\$ I think the problem is OK, but people might just do this by multiplying regular polynomials and then combining x^(n+i) with x^i. I like the group idea, but I've already done the quaternions. \$\endgroup\$ – xnor Mar 23 '15 at 4:03
  • \$\begingroup\$ @xnor Well, for the quaternions it wouldn't be as simple. Perhaps I could stipulate that one of the answers to your problem should be used in some way? \$\endgroup\$ – ymar Mar 23 '15 at 4:16
  • \$\begingroup\$ What do you mean that it wouldn't be as simple? \$\endgroup\$ – xnor Mar 23 '15 at 4:20
  • \$\begingroup\$ @xnor I mean that it wouldn't be just a simple variation on polynomial multiplication. It's still similar because that's what the (semi)group ring multiplication is: a generalization of polynomial multiplication. But the case of the quaternion group is further away from polynomials than cyclic groups. \$\endgroup\$ – ymar Mar 23 '15 at 4:24
1
\$\begingroup\$

Functioning HTML-Encoded Program


Introduction

When showing code to others on the web, some characters are generally replaced by their HTML-encoded entities. Browsers display this properly, but if a user copies the code directly from HTML or a script tries running the code without decoding its entities, the code will likely contain errors.

Challenge

You are to come up with a program that uses all of the following five characters: ", &, ', <, and >. When encoded to their named XHTML entities, the code must still run using the following respective entities: &quot;, &amp;, &apos;, &lt; and &gt;. The code must be able to run both ways without throwing errors. Each of the five characters must be used outside of comments and string-like objects at least once (ie. for JS, outside of literal regex). You may use an expression in place of a statement up to one time (if your language supports it).

Example JS Script (1/5 required characters)

Unencoded: (Sets lt to true)

var lt = 6;
lt = 3 < lt;

Encoded: (Sets lt to 2)

var lt = 6;
lt = 3 &lt; lt;

Encoder/Decoder

Here's a converter to make testing your code easy (click run code to use):

function encode() {
  document.getElementById('post').value = document.getElementById('pre').value.replace(/&/g, '&amp;').replace(/"/g, '&quot;').replace(/'/g, '&apos;').replace(/</g, '&lt;').replace(/>/g, '&gt;');
  if (entity=document.getElementById('pre').value.match(/&\S+?;/)) alert('Warning: Unencoded text may already have entities. (ie: ' + entity[0] + ')');
} function decode() {
  document.getElementById('pre').value = document.getElementById('post').value.replace(/&quot;/g, '"').replace(/&apos;/g, '\'').replace(/&lt;/g, '<').replace(/&gt;/g, '>').replace(/&amp;/g, '&')
  if (entity=document.getElementById('post').value.match(/&(?:[\s;]|[^\s;]*(?:\s|$))|<|>|'|"/)) alert('Warning: Encoded text may contain unencoded characters. (ie: ' + entity[0][0] + ')');
}
<label for="pre"><b>Unencoded:</b></label> <button onclick="encode()">Encode</button><br /><textarea id="pre" style="width:100%;min-height:49px;resize:vertical"></textarea><br /><br />
<label for="post"><b>Encoded:</b></label> <button onclick="decode()">Decode</button><br /><textarea id="post" style="width:100%;min-height:49px;resize:vertical"></textarea>

The shortest functioning unencoded code block wins. Have fun!

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ I would vote to close this as too broad, because as far as I can tell from the question, all the program has to do is not crash. It probably wouldn't be a good question even with a spec which required it to perform a stated task, though, because it's so easy to bypass the intent by using no-ops. \$\endgroup\$ – Peter Taylor Mar 27 '15 at 23:37
  • \$\begingroup\$ @PeterTaylor That was the point of me including "You may use an expression in place of a statement up to one time (if your language supports it)," but I suppose that I can't assume that'll cover every case of no-ops in programming languages out there. \$\endgroup\$ – Pluto Mar 30 '15 at 19:40
1
\$\begingroup\$

Print All Provable Statements

This might be a stretch to make into a challenge, but I think it can be done. The challenge will most likely be code-golf. I'm thinking about using 2D geometry as the basis. I will have to create a notation system for geometrical and logical statements that is golf-friendly.

The general idea is that you start off with a list of known facts. Then, the program uses the laws of logical deduction to work through every possible deduction that can be made, and then add these new facts back into the pool of knowledge. Given enough time, every possible provable statement will show up in your list. Of course, you will run out of memory first, and that's okay.


Probably the best axioms to use are Tarski's Axioms. From the wiki article:

Tarski's system has the unusual property that all sentences can be written in universal-existential form, a special case of the prenex normal form. This form has all universal quantifiers preceding any existential quantifiers, so that all sentences can be recast in the form

∀u∀v...∃a∃b...

This fact allowed Tarski to prove that Euclidean geometry is decidable: there exists an algorithm which can determine the truth or falsity of any sentence. Tarski's axiomatization is also complete. This does not contradict Gödel's first incompleteness theorem, because Tarski's theory lacks the expressive power needed to interpret Robinson arithmetic (Franzén 2005, pp. 25–26).

There are three (?) fundamental relations:

  • x=y Equality - x and y refer to the same objects
  • Bxyz Betweenness - The point z is between x and z, lying on line segment xz. It is possible for x=y or y=z.
  • wx~yz Congruence - The length of line segment wx is equal to the length of line segment yz.

There are three congruence axioms:

  • xy~yx Reflexivity of Congruence
  • xy~zz → x=y Identity of Congruence
  • xy~zu & xy~vw → zu~wz Transitivity of Congruence

There are also betweenness axioms:

  • Bxyx → x=y Identity of betweenness
  • Bxuz & Byvz → ∃a(Buay & Bvax) Axiom of Pasch
  • Axiom Schema of Continuity: I'll need some help translating this.
  • ∃a∃b∃c(!Babc & !Bbca & !Bcab) Lower Dimension

And some more:

  • (xu~xv & yu~yv & zu~zv & u!=v) → (Bxyz | Byzx | Bzxy) Upper Dimension
  • (Bxuv & Byux & x!=u) → ∃a∃b(Bxya & Bxzb & Bavb) Equivalent to Euclid's Axiom
  • (x!=y & Bxyz & Bfgh & xy~fg & yz~gh & xu~fi & yu~gi) → zu~hi Five Point
  • ∃z(Bxyz & yz~ab) Segment Construction

Some notes on mathematical notation.

I think it would be a good idea to convert all math notation to ASCII. I've done with with congruence already, but I need replacements for → ∃ ∀. I might replace a!=b with !a=b for consistency, or I could go all-out and put everything in Polish notation.


If I wanted fancier axioms

Here is an alternative set of axioms, which are based on Hilbert's geometry axioms but excluding the ones that talk about planes. Some of them are copied verbatim from that website and may be unnecessarily fluffy. I would have to re-write all of them to be in formal notation.

  1. Given two distinct points A and B, then there exists exactly one line a that contains both points.
  2. Given a line a, there exist at least two distinct points A,B which lie on the line and three distinct points X,Y,Z which are not on the line.
  3. If a point B lies between points A and C, then points A,B,C are three distinct points on a line, and B also lies between C and C.
  4. For two distinct points A and C, there exists at least one distinct point B such that C lies between A and B.
  5. Of any three points on a line, there exists no more than one that lies between the other two.
  6. Let A, B, C be three points that do not lie on a line and let a be a line which does not meet any of the points A, B, C. If the line a passes through a point of the segment AB, it also passes through a point of the segment AC, or through a point of the segment BC.
  7. If A, B are two points on a line a, and A' is a point on the same or on another line a' then it is always possible to find a point B' on a given side of the line a' through A' such that the segment AB is congruent or equal to the segment A'B'. In symbols AB = A'B'.
  8. If a segment A'B' and a segment A"B", are congruent to the same segment AB, then the segment A'B' is also congruent to the segment A"B", or briefly, if two segments are congruent to a third one they are congruent to each other.
  9. On the line a let AB and BC be two segments which except for B have no point in common. Furthermore, on the same or on another line a' let A'B' and B'C' be two segments which except for B' also have no point in common. In the case, if AB = A'B' and BC = B'C' then AC = A'C'.
  10. Let angle(h,k) be an angle and a' a line and let a definite side of a' be given. Let h' be a ray on the line a' that emanates from the point O'. Then there exists one and only one ray k' such that the angle(h,k) is congruent or equal to the angle(h',k') and at the same time all interior point of the angle(h',k') lie on the given side of a'. Symbolically angle(h,k) = angle(h',k'). Every angle is congruent to itself, i.e., angle(h,k) = angle(h,k) is always true.
  11. If for two triangles ABC and A'B'C' the congruences AB = A'B', AC = A'C', angleBAC = angleB'A'C' hold, then the congruence angleABC = angleA'B'C' is also satisfied.
  12. Let a be any line and A a point not on it. Then there is at most one line in the plane, determined by a and A, that passes through A and does not intersect a.
  13. If AB and CD are any segments, then there exists a number n such that n segments CD constructed contiguously from A, along the ray from A through B, will pass beyond the point B.
  14. An extension of a set of points on a line with its order and congruence relations that would preserve the relations existing among the original elements as well as the fundamental properties of line order and congruence that follow from Axioms I-III, and from V,1 is impossible.
| |
\$\endgroup\$
1
\$\begingroup\$

Here's a puzzle to be split into two questions:

Build an evil-defying Tetris AI

Build a program that takes the state of a current board and a piece and attempts to find the optimal space for it.

Your program will be scored by the number of points it can score against the evil Tetris block generators in the question below. Highest score wins. (scoring algorithm to come later)

Build an evil Tetris block generator

Build a program that attempts to take the state of a current board and generate the worst possible piece for it.

Your program will be scored by the total number of points the AIs built in the question above can score against it. Lowest score wins.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ In general, if you mainly flood with S and Z then it's basically unsolveable. Also related :) \$\endgroup\$ – Sp3000 Apr 6 '15 at 13:44
1
\$\begingroup\$

It's just a flesh wound!

The idea is to create a program that:

  • If any one of the four quarters (counted in bytes) is removed, the program outputs "Tis' but a scratch" (exactly, with optional newline).
  • If any two of the four quarters are removed, the program outputs "Just a flesh wound.".
  • If any three of the four quarters are removed, the program outputs "Let's call it a draw, then.".
  • The full program should output "None shall pass.".

Rules:

  • The program has to have length divisible by four (4).
  • The program must not read it's own source or it's length in any way.
  • The output is to stdout if it is possible in your language (REPL output is considered valid in this case).
  • The answer with the fewest bytes wins.
| |
\$\endgroup\$
  • \$\begingroup\$ I don't think this would actually be a duplicate of anything in the source-layout tag, but it doesn't feel like it would add anything to the sum of what's already in that tag. \$\endgroup\$ – Peter Taylor Mar 19 '15 at 19:17
  • \$\begingroup\$ Would these 'quarters' be defined by the user, or is it any random 1/4th of the program? \$\endgroup\$ – ASCIIThenANSI Apr 5 '15 at 16:49
  • \$\begingroup\$ @ASCIIThenANSI The quarters are successive quarters of the code. ie. the first one is 0 - 1/4, second is 1/4 - 2/4, third is 2/4 - 3/4 and fourth is 3/4 - 4/4 \$\endgroup\$ – seequ Apr 5 '15 at 17:48
  • \$\begingroup\$ Would it be allowed to read the program's own length? \$\endgroup\$ – ASCIIThenANSI Apr 7 '15 at 13:03
  • \$\begingroup\$ @ASCIIThenANSI No. Updated. \$\endgroup\$ – seequ Apr 7 '15 at 14:50
  • \$\begingroup\$ Here's an idea: If it is full, it prints None shall pass., one-quarter, Tis' but a scratch., and three-quarters, Let's call it a draw, then.. \$\endgroup\$ – ASCIIThenANSI Apr 7 '15 at 14:55
  • \$\begingroup\$ @ASCIIThenANSI Awesome. \$\endgroup\$ – seequ Apr 7 '15 at 15:41
1
\$\begingroup\$

Programming Tetris Blocks (Even More Literally?)

In this challenge, you will write a Tetris AI. There's one twist though: the AI will operate from the perspective of the Tetris blocks themselves.

Note: I am worried about the novelty of this question. The key is "the perspective of the Tetris blocks themselves." In order to make this interesting, I have to give the AI a bare minimum of information needed to make a move. Otherwise, it will just be a regular Tetris AI challenge.

When a Tetris block is spawned at the top of the map, a new AI object is created. Each time step, and the block receives data about its immediate surroundings and returns a move (move left/right, rotate clockwise/counterclockwise, or nothing).

An idea as to "block vision": each of the four squares in a block each have four "eyes," one on each side. Each eye returns the distance to the nearest wall/block (including/excluding other squares in the same block?). This means that the AI will receive exactly sixteen numbers each update.

#######
# 1234#
#  #  #
#### ##
#######

If a 2D array where each row (1st level) is a square and each column (second level) is an eye in the directions [U,D,L,R], then here is what could be seen as input, with 0s representing an adjoining block.

[[1,2,2,0],[1,1,0,0],[1,3,0,0],[1,2,0,1]]

More details coming sometime not now.

| |
\$\endgroup\$
  • \$\begingroup\$ For 'block vision', what if returns -1 if it hits the same block? Also, shouldn't the squares be numbered left to right and up to down, so the I piece is [1][2][3][4], and an example 'block vision' would be [1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 4, 4, 4, 4, 2, 2]? \$\endgroup\$ – ASCIIThenANSI Apr 14 '15 at 16:24
  • \$\begingroup\$ @ASCIIThenANSI In your example, which numbers refer to which squares/eyes? \$\endgroup\$ – PhiNotPi Apr 14 '15 at 16:49
  • \$\begingroup\$ Square 1 is the first 4 numbers ([1, 2, 3, 1]), square 2 the next 4 ([2, 3, 1, 2]), etc. The directions are in the format [U, D, L, R], and it works like [U, D, L, R, U, D, L, R, U, D, L, R, U, D, L, R]. \$\endgroup\$ – ASCIIThenANSI Apr 14 '15 at 17:10
  • \$\begingroup\$ I couldn't really visualize where you were getting the numbers from, so I added my own example. \$\endgroup\$ – PhiNotPi Apr 14 '15 at 17:27
1
\$\begingroup\$

Traffic Troubles

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.

| |
\$\endgroup\$
1
\$\begingroup\$

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

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?

| |
\$\endgroup\$
1
\$\begingroup\$

KotHgress

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.
| |
\$\endgroup\$
  • \$\begingroup\$ I understand that a > z, A > a, and A > Z. But which would be greater: a or Z? And is the bot with voice a placed before or after the bot with voice b? \$\endgroup\$ – ASCIIThenANSI May 15 '15 at 13:10
  • \$\begingroup\$ I was figuring on going in ascii order, so `A->Z->a->z'. That allows for 52 committee members; I can do non-alphas if we get more interest than that, lol. \$\endgroup\$ – sirpercival May 15 '15 at 13:33
  • \$\begingroup\$ OK. Just make sure that you add that to the rules. You could also use some of ASCII's 95 printable characters (minus space, and maybe take out some others that could mess up the input.) \$\endgroup\$ – ASCIIThenANSI May 15 '15 at 13:43
  • \$\begingroup\$ I'll be a little more specific about this, sure. \$\endgroup\$ – sirpercival May 15 '15 at 15:02
  • \$\begingroup\$ This has the classic KotH flaw: the best strategy is either to be purely random or to be the last person to submit your bot, and to metagame it against everyone else's bots. \$\endgroup\$ – Peter Taylor May 17 '15 at 16:01
  • 1
    \$\begingroup\$ how would one metagame? the priority order is randomized at the beginning of each meeting \$\endgroup\$ – sirpercival May 17 '15 at 16:19
1
\$\begingroup\$

Time Travel in KotH

This is not a question but a possible mechanic for KotH (type 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...)

| |
\$\endgroup\$
1
\$\begingroup\$

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.

| |
\$\endgroup\$
  • \$\begingroup\$ This is basically like a previous suggestion I made, but less complicated. My main motivation had been parsing Japanese kanji compounds, hence the unicode support, but I translated it into something more familar to non-Japanese speakers. \$\endgroup\$ – blutorange May 20 '15 at 19:21
1
\$\begingroup\$

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.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I take it there aren't any limitations on efficiency? I seem to remember it's an open problem whether HAM-PATH is hard on subgraphs of the grid graph, and if so, you won't be getting an poly-time algorithms. \$\endgroup\$ – xnor May 22 '15 at 9:13
  • \$\begingroup\$ @xnor Yes, no limitations on time/efficiency \$\endgroup\$ – Arnaud May 22 '15 at 11:59
1
\$\begingroup\$

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

| |
\$\endgroup\$
  • \$\begingroup\$ The meat of this challenge is basically just the reverse of this one, which may explain why you haven't seen it this way. \$\endgroup\$ – Geobits May 27 '15 at 16:07
  • \$\begingroup\$ "The input can be in any format, not just integers." is far too vague. "The output must be rounded if too long." needs to define "too long", and ideally give a rounding rule (e.g. floor, ceiling, nearest half-up, nearest half-down, nearest half-even, nearest half-odd). \$\endgroup\$ – Peter Taylor May 30 '15 at 13:46
  • \$\begingroup\$ Thanks, sorry I'd missed the first answer, that is quite similar haha. This one should use 10x the values and may golf better with outputting the number instead of reading the input. And is the rounding rule actually needed? I generally meant what the default rounding functions do (that you learn in school), which is like half up, but then half down when you're below 0. \$\endgroup\$ – Peter May 31 '15 at 8:45
  • \$\begingroup\$ Ended up busy with other stuff recently so only just remembered about this, would it be worth posting, or is it too similar to that other question? \$\endgroup\$ – Peter Jul 13 '15 at 21:46
1
\$\begingroup\$

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
| |
\$\endgroup\$
1
\$\begingroup\$

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.

| |
\$\endgroup\$
  • \$\begingroup\$ Are you planning a follow-up which asks people to generate minimal covering arrays? That seems to be the more interesting direction. \$\endgroup\$ – Peter Taylor Jun 11 '15 at 5:31
  • \$\begingroup\$ @PeterTaylor that's actually a cool idea, but other than v=t=2, the minimal case is not known, and no explicit construction is known (other than orthogonal arrays, which only work for one value of k). One question could be to ask for the best known minimal CA, which is actually something I'd really like (because it is part of my research). \$\endgroup\$ – Ryan Jun 11 '15 at 11:46
  • \$\begingroup\$ I was thinking of a code-challenge which scores by the best CA for certain parameters, possibly required to be deterministic and inside a certain time limit. \$\endgroup\$ – Peter Taylor Jun 11 '15 at 12:33
  • \$\begingroup\$ @PeterTaylor I like that idea, possibly allowing any technique such as simulated annealing. \$\endgroup\$ – Ryan Jun 11 '15 at 21:02
1
\$\begingroup\$

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

| |
\$\endgroup\$
  • \$\begingroup\$ "Any pieces that the board will be deleted" Did you mean "Any pieces that the board contains will be deleted"? Also, your KOTH seems to have too much boldness . Use bacticks(`) instead of bold for code formatting and try to use bold whenever appropriate.. \$\endgroup\$ – Spikatrix Jun 12 '15 at 4:54
  • 2
    \$\begingroup\$ From your description of the move method, it sounds like an entry has the opportunity to change data that it shouldn't be allowed to change. We all tend to be sportsmanlike here, and I'm sure nobody would try to game the system like that, but you should try not to make such things available. And anyway, if somebody tries to obfuscate their code, or has a bug, an accident could end up catastrophic. I don't know how rigorous your movechecking will be, but be careful. \$\endgroup\$ – BrainSteel Jun 12 '15 at 5:12
  • 1
    \$\begingroup\$ What size is the board? Does a piece which gets level with the rearmost of the opponent's pieces become irrelevant except as a guarantee that you can't lose? \$\endgroup\$ – Peter Taylor Jun 12 '15 at 8:57
  • \$\begingroup\$ Thank you for your feedback everyone. CoolGuy: My apologies for over-bolding, will fix. I was editing in another editor, not on StackExchange. @BrainSteel I will play around with various ways of making sure moves are not illegal. Any ideas for how I can make it impossible to unfairly change the board? I'm not very sure about this one, and I'll have a look at other KOTHs to see how they handle it. If you have any suggestions please let me know. Peter Taylor: The size of the board is 8x8. \$\endgroup\$ – Matt Y Jun 13 '15 at 3:51
  • \$\begingroup\$ @BrainSteel I have now finished a system for checking the move which should stop people from changing the board. They receive a local copy of the board and must submit it back with submitBoard (hence now move() is a void). So now I can do move checking. There will also be a method called verify which will verify the board. \$\endgroup\$ – Matt Y Jun 13 '15 at 5:52
  • \$\begingroup\$ Thanks, that looks like a fine way to handle it! You can never be too careful. I await your controller! \$\endgroup\$ – BrainSteel Jun 13 '15 at 15:48
  • \$\begingroup\$ Some diagrams/images would really help clarify the rules- for example the starting set up - I assume each player starts with two rows of pieces at their end of the board but this is not clear. Also a diagram showing the allowable moves would be really great. What happens when one of your pieces reaches the opposite edge of the board and cannot be taken. Other than that looks like a really interesting challenge and looking forward to it... :) \$\endgroup\$ – euanjt Jun 13 '15 at 16:38
  • \$\begingroup\$ Thanks for the feedback! @TheE Controller is on its way. Might take a while... I code as slow as a tortoise ;) \$\endgroup\$ – Matt Y Jun 13 '15 at 22:31
  • \$\begingroup\$ I don't think the themed intro adds anything. \$\endgroup\$ – mbomb007 Dec 12 '16 at 16:07
1
\$\begingroup\$

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
| |
\$\endgroup\$
  • \$\begingroup\$ I'm surprised this hasn't been asked before, but I can't find it. Is code challenge (with codegolf tie break) the best scoring? I'm not sure about making it a codegolf, because I think the higher n are probably quite hard and it would discourage participation. \$\endgroup\$ – Level River St Jun 14 '15 at 10:27
  • \$\begingroup\$ Do enantiomers count twice? \$\endgroup\$ – feersum Jun 15 '15 at 5:37
  • \$\begingroup\$ "Your task is to create a program or function that accepts a single integer 0 < n < 12 ... The winning entry will be the program that produces correct output for the highest value of n ... Above n=11 there exist some isomers ... that cannot be represented according to the rules of this question" What I understand from this is that every valid submission gets the same score, which seems a bit pointless. With the given tie-breaker, it's effectively just a code-golf. \$\endgroup\$ – Peter Taylor Jun 15 '15 at 7:13
  • \$\begingroup\$ @PeterTaylor I've changed it to a codegolf for n=9, plus a generous bonus for n=11. n>9 is fiddly (more for display reasons than underlying maths) because sometimes the sidechains have sidechains. I want to see all the way to n=11, but I don't want to exclude people by making it too hard. \$\endgroup\$ – Level River St Jun 15 '15 at 14:20
  • \$\begingroup\$ @feersum to avoid complication, enantiomers and other types of stereoisomers are considered equivalent, you should only include one of them for each structural isomer. In any case they can't be distinguished properly according to the display spec. Bond symbols such as < and > would be needed to show whether an atom is closer/further than another. I thought this was clear from rule 3 and example 3,4 dimethyloctane, but I'm not surprised someone asked. Is there a way to make this clearer? \$\endgroup\$ – Level River St Jun 15 '15 at 14:28
1
\$\begingroup\$

Solve the nonogram

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

| |
\$\endgroup\$
  • \$\begingroup\$ You really need some time limit on this, and for a specified size. "don't try to brute force it" is vague. The shortest-code way of solving this will be to try every possible combination of 0's and 1's and check. That will take less than a second for example 1, a lifetime for example 2, and something like the current age of the universe for example 3. There are other marginally less naive ways of doing it, like generating all possible rows then checking the colums, which will also take too long. I'd go as far as to say this might go better as fastest code (largest example solved in 1 minute.) \$\endgroup\$ – Level River St Jun 16 '15 at 13:55
  • \$\begingroup\$ Did you make that batman yourself? Are you sure it's the only valid solution? (doesn't matter so long as you specify that the program can terminate when it finds any valid solution.) Note that a human will immediately note the completely full rows and the (near) symmetry, which it will make it easier, while a computer will not. \$\endgroup\$ – Level River St Jun 16 '15 at 14:00
  • \$\begingroup\$ @steveverrill I was thinking of 2~3 minutes for the 30*30 one, I don't want it to take some billion years :). But I'll take your fastest code in consideration, as it may have more sense, and could be interesting to see what people will bring. \$\endgroup\$ – Katenkyo Jun 16 '15 at 14:25
  • \$\begingroup\$ @steveverrill Yes I did, and there shouldn't be any other solution. But as per the rules of a nonogram, any solution satisfying lines/columns is a good one, just less prettier than the intended one. Using symettry is useless to solve this one. I solved it only using the "30 is length of the row, I fill", "27 2 means w+27+x+2+y=30, 30- 27+2=29 so w=y=0 and x=1" plus an other strategie designed as "simple boxes" on the wikipedia page. This is the basic movement a beginner learn, and they shouldn't be hard to code them as they can be done line-by-line and column-by-column \$\endgroup\$ – Katenkyo Jun 16 '15 at 14:30
  • \$\begingroup\$ Are you sure your 30x30 has only one solution? \$\endgroup\$ – Sparr Jun 16 '15 at 15:15
  • \$\begingroup\$ @Sparr I'm still testing to find other ones, but I can't find an other one \$\endgroup\$ – Katenkyo Jun 16 '15 at 16:44
  • 1
    \$\begingroup\$ I see you're aware fastest code means you must take reponsibilty for running the code. Score should either be: 1. time to solve a given grid size, or 2. max (square?) grid size solved in a given time. simply "fastest code" is not enough. The trouble with 1 is you've no idea how long it will take (see meta.codegolf.stackexchange.com/q/5360/15599). The trouble with 2 is you may have to define additional grids, but I think that's preferable over 1. Users can time themselves on the test cases to give an idea of the winner - probably there will be vast differences in timing.. \$\endgroup\$ – Level River St Jun 16 '15 at 19:40
  • \$\begingroup\$ @steveverrill I'm going for 2., surely with a 60*60 or 70*70 grid (would be hard to design a greater one). I think it has enough cells to see who's the best. If not, i'll push myself into a 90*90 one. \$\endgroup\$ – Katenkyo Jun 17 '15 at 7:05
  • \$\begingroup\$ According to Wikipedia this problema is NP-hard. That means grid size will have a massive impact on time. It's not at all clear whether 30x30 will run in reasonable time. If you want to score by time to complete a certain grid, I suggest you start with the smallest grid, eliminate all entries that run a measurable time (say 1 second) slower than the leader, then proceed to do the same with larger and larger grids until only one entry remains. That way you can avoid the problem of timings that are ridiculously fast or ridiculously slow. It also means the entries get tested on a variety of grids \$\endgroup\$ – Level River St Jun 17 '15 at 9:07
  • \$\begingroup\$ Oops- just seen the new note about "solveable without any guess"! If anyone encodes an algorithm for that (I'm guessing a máximum of 2 people will do that, it's easy for a human to do but quite difficult to code) it should run very fast. If it is guaranteed that no guessing is required this becomes quite a different challenge. Is it guaranteed? \$\endgroup\$ – Level River St Jun 17 '15 at 9:16
  • \$\begingroup\$ @steveverrill I might try to code a submission, to see how much time it would take. It could be used by others as a scale to see how far they are from it. A real nonogram must be solved by logic only. It can be complicated logic (while you predict what 2+ boxes placed would do on the board(depth-reasoning)). I don't think I'll be able to prove that point, but I tried for those 3 every way I could to solve them, and each time no guesses were needed. That's the reason it is long to design one ^^'. \$\endgroup\$ – Katenkyo Jun 17 '15 at 9:23
  • \$\begingroup\$ The challenge is currently self-contradictory, asking "Who will find the best heuristics?" but promising "they are all solvable using basic techniques." If it is going to be a fastest-code and not a code golf, then the puzzles should be as difficult as possible. \$\endgroup\$ – feersum Jun 18 '15 at 22:26
  • \$\begingroup\$ @feersum The fact they are all solvable by basics is because it was initially a code-golf. The 60*60 I'm designing will be a bit more trickier to solve, and I might prepare a 40*40 as an intermediate tricky case. But yeah, thanks for denoting this fact, I might have forgotten. \$\endgroup\$ – Katenkyo Jun 19 '15 at 7:12
  • \$\begingroup\$ i know this game and i cant solve it another way aside bruteforce, sorry but i thnk this challenge wouldnt give desired results \$\endgroup\$ – Abr001am Jun 25 '15 at 10:50
1
\$\begingroup\$

4-Way Intersection Simulator

Consider an intersection as follows:

enter image description here

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.
| |
\$\endgroup\$
1
\$\begingroup\$

Black and White Morphing

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.

enter image description here enter image description here enter image description here enter image description here enter image description here

| |
\$\endgroup\$
  • \$\begingroup\$ Is the stark contrast how you want to the challenge to look, or just what you happen to have at the moment? How would you feel about including dithered images that use the same number of white pixels as these but give the impression of grayscale, and make more detail visible in the currently pure black and pure white regions? \$\endgroup\$ – trichoplax Jun 20 '15 at 21:04
  • \$\begingroup\$ Would it provide more challenge and more variety to include more than one value for number of white pixels? Perhaps the same 5 images could be provided in 3 categories: black heavy, white heavy and balanced. Then the results for each category can be shown so we can judge whether a given technique gives good results across the board. \$\endgroup\$ – trichoplax Jun 20 '15 at 21:07
  • \$\begingroup\$ Of course there should be more series, and I like your suggestion of black heavy, white heavy and balanced. My idea way that people should come up with creative transitions from one image to the other and back, I imagined something like the 'powerponit' slide transitions. The images are black and white only for making the challenge somewhat easier. \$\endgroup\$ – flawr Jun 20 '15 at 21:09
  • \$\begingroup\$ I like the restriction to black and white only. I don't necessarily think it makes it easier, but I think restriction is very important for popularity contests otherwise they get too open ended. It might be worth adding more restriction otherwise it risks being closed as too broad. For example, you might restrict how much difference there can be from one frame to the next. Maybe only 5% of pixels can change each frame (or whatever percentage you feel is best). You might feel that particular restriction detracts from some potential solutions so that's just an example. \$\endgroup\$ – trichoplax Jun 20 '15 at 21:31
  • \$\begingroup\$ The answers to this question might have some useful code for creating nice dithered images for your sample images. It converts greyscale to strictly only black and white. \$\endgroup\$ – trichoplax Jun 20 '15 at 21:55
  • \$\begingroup\$ It might be worth thinking up a few examples of transition effects and then adding restrictions that don't rule out any of the effects you thought of. To make it an interesting challenge but without losing potential answers. \$\endgroup\$ – trichoplax Jun 20 '15 at 21:56
  • \$\begingroup\$ For example, the effect of paint running down from the top of the picture overwriting the old picture with the new. \$\endgroup\$ – trichoplax Jun 20 '15 at 21:57
  • \$\begingroup\$ Or a simple slide across (with or without the old image moving too). \$\endgroup\$ – trichoplax Jun 20 '15 at 21:58
  • \$\begingroup\$ Or "burn through" from a hole appearing in the centre, like old cinema projectors if left on one frame too long. \$\endgroup\$ – trichoplax Jun 20 '15 at 21:59
  • 4
    \$\begingroup\$ Cf codegolf.stackexchange.com/q/33172/194 , although the morphs there don't preserve the number of pixels of each colour in the intermediate frames. At present I would vote to close this as too broad, and suggest adding a restriction that in each frame the changed pixels must pair up into adjacent pairs which swap with each other. \$\endgroup\$ – Peter Taylor Jun 20 '15 at 22:01
  • \$\begingroup\$ @PeterTaylor I was aware of that challenge (I did even participate=), but I did not realize that this one would be so similar to the other one. I really like your idea of the swapping restriction, but I am not sure whether this is perhaps too restrictive. Another idea I had (very vague so far) is considering the white pixels as some kind of 'fluid' that can only move with a certain velocity (or another property) and your suggestion would really match that idea. The question is for each frame transition, should we limit the number of swaps? Or the number of swaps per pixel? \$\endgroup\$ – flawr Jun 21 '15 at 10:04
1
\$\begingroup\$

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

| |
\$\endgroup\$
  • \$\begingroup\$ Can we assume our language's built-in sorting is O(n lg n)? \$\endgroup\$ – xnor Mar 5 '15 at 2:58
  • \$\begingroup\$ @xnor Usually they are O(n lg n). But if you meant some language with a built-in sorting function not in O(n lg n) (or nobody is bothered to check the real complexity), I'm not sure. Strictly speaking they may be not in O(n lg n) and invalid. But it seems nobody is downvoting or deleting those answers. \$\endgroup\$ – jimmy23013 Mar 5 '15 at 4:38
  • \$\begingroup\$ @user23013 They are very rarely O(n log n). Most languages implement quick sort, which is O(n log n) on average but has a worst case complexity of O(n^2). That being said, I'd always include a statement along the lines "you may assume that your language's built-in sorting function runs in O(n log n)". \$\endgroup\$ – Martin Ender Mar 6 '15 at 21:10
  • \$\begingroup\$ @MartinBüttner Allowed expected complexity. Is it better now? \$\endgroup\$ – jimmy23013 Mar 7 '15 at 2:06
  • \$\begingroup\$ I don't know... it just seems unnecessarily complicated to me and puts some esolangs at a disadvantage that might have a naive sort implementation, but ultimately it's your call. \$\endgroup\$ – Martin Ender Mar 7 '15 at 2:09
  • \$\begingroup\$ @MartinBüttner Do you have ideas about the stronger version (allowing inserting (a,b) dynamically)? I'm trying to make it consistent. And esolangs can answer the convex hull question anyway. \$\endgroup\$ – jimmy23013 Mar 7 '15 at 2:41
  • \$\begingroup\$ @user23013 I don't think I'm qualified to have an opinion about the stronger version. ;) \$\endgroup\$ – Martin Ender Mar 7 '15 at 3:02
1
26 27
28
29 30
99

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .