461
\$\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\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43

2619 Answers 2619

2
\$\begingroup\$

Times have changed!

(pun intended)


Preface

As mathematics progressed, mathematicians agreed upon the 'order of operations', to prevent mathematical expressions from becoming ambiguous.

Given the expression \$7 \times 6 + 5 \times 3\$ we know to first evalulate multiplication, giving \$ 42 + 15\$, which is equal to \$57\$.

But what if another group of mathematicians had agreed to evaluate addition before multiplication? This expression would become \$ 7 \times 11 \times 3\ = 231\$: which is different from our answer by an error of \$305\%\$!


The Challenge

Given a mathematical expression containing + (addition), * (multiplication), and the digits 0123456789, we can find:

  • \$E_1\$ - the 'real' value of the expression, when multiplication takes precendence.
  • \$E_2\$ - the 'alternate' value of the expression, when addition takes precedence.

Your task is to write a program or function which, given a string representing an expression, calculates and outputs the percentage error, \$\frac{|E_1 - E_2|}{E_1} \times 100\$.


Rules

  • WIP.
\$\endgroup\$
2
\$\begingroup\$

Roll for Initiative!

Tags:

Introduction

In tabletop games like Dungeons and Dragons, when you begin a battle, all involved parties roll for initiative. In DnD 5e, this is 1d20 + DEX + Other bonuses, where DEX is the bonus given by your Dexterity stat. The characters that roll higher numbers go first. We'll use a similar, deterministic system in this challenge.

The Challenge

Write a program or function that, when given a list of characters, will output a list of characters in order of initiative.

A character is defined as this:

character = {
    name: "name" // a string
    statblock: [SPD, DEX, WHT] // a list of numbers
                               // DEX = dexterity, SPD = speed, WHT = weight
}

The formula for initiative is the following: $$\text{Initiative} = \left\lfloor{ \frac{\text{SPD}^2}{\sqrt{\lvert\text{DEX}\rvert}} }\right\rfloor - \text{WHT}$$

Input

A list of characters, unsorted. This can be a JSON object, a list of lists, a list of dictionaries, a series of strings etc.

It is guaranteed that all names will be unique.

Output

A list of characters, or character names, sorted by initiative order from highest to lowest, based on the above formula.

Rules

Sample IO

Input --> Output
[[Name, SPD, DEX, WHT], ...]
    --> [[Name, SPD, DEX, WHT], ...] (or [Name, Name, ...])
---------
[[Alice,1,2,3],[Bob,10,5,0],[Charlie,3,2,1]]
    --> [Bob, Charlie, Alice]
// Alice = -3, Bob = 44, Charlie = 5

[[Z,1,1,1],[B,1,1,1],[XY,5,1,1]]
    --> [XY, Z, B]
// Retain the order of characters from the input if they have the same initiative.
// Z = 0, B = 0, XY = 24

[[Neg,-3,-3,-1],[SomeNeg,5,-2,-4],[NoNeg,4,6,8]]
    --> [SomeNeg, Neg, NoNeg]
// Negative values are valid.
// Neg = 6, SomeNeg = 13, NoNeg = -2

[[Flo,1.5,2.5,3.5],[MoreFlo,2,2.5,3.5]]
    --> [[MoreFlo,2,2.5,3.5], [Flo,1.5,2.5,3.5]]
// Floats are also valid.
// Flo = -2.5, MoreFlo = -1.5

[[Lonely,1,2,3]]
    --> [[Lonely,1,2,3]]
// Input with 1 item.

[]
    --> []
// Empty input leads to empty output.
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use \left and \right in mathjax to make your brackets the right size. I also think that the output format is a little pointlessly strict - why not also allow just the list of names (same with requiring stable sorts)? \$\endgroup\$ – FryAmTheEggman Dec 4 at 23:11
2
\$\begingroup\$

Golfing with 2s

It is well-known that all positive integers can be represented via a sum of powers of 2. For example, 13=2^3+2^2+2^0. We can rewrite the 3 and 0, to get 13=2^(2+2/2)+2^2+2^(2-2). A shorter representation might be 13=2^2^2-2-2/2, or a more repetitive one 13=2+2+2+2+2+2+2/2

Challenge

Your task is, given a nonnegative integer as input, output a string containing only 2 and elementary operations, which when evaluated will yield that integer. These operations are +, -, *, /, ^, and appropriate parentheses.

However, the string should tend to be one of the shorter representations of the integer in question. So for the above example with 13, 2^2^2-2-2/2 and 2^2^2-2/2-2 are the shortest representations.

The input can be in any convenient format, but the output must be in the above format, either to a file or STDIO.

Scoring

Short code and efficient representation are both prioritized, so the score is the length in bytes plus the average length of the returned string for 9, 57, 554, 1894, 25993, 113193, 2998225, and 52748566.

Rules

Standard loopholes not allowed

Standard input/output forms apply

Some degree of brute forcing is allowed, but the program must handle larger inputs in reasonable time.

Example outputs

0            2-2
1            2/2
2            2
3            2+2/2
4            2^2
5            2^2+2/2
6            2^2+2
7            2^2+2+2/2
8            2*2*2
9            2*2*2+2/2
10           2*2*2+2
57           2^(2^2+2)-2^2-2-2/2
554          2*2^(2*2*2)+2*2^2^2+2*2*2+2
1894         2*2^(2*2*2+2)-(2^2^2-2)*(2*2*2+2+2/2)
25993        (2*2^(2*2*2+2)-2*2^(2*2*2)-2^2-2-2/2)*(2^2^2+2/2)
113193       2*2^2^2^2-(2^(2*2*2+2)-2^(2^2+2)-2^2^2-2-2/2)*(2^2^2+2+2/2)
2998225      (2*2^2^2^2-(2^(2*2*2+2)-2*2*2-2-2/2)*(2*2*2+2+2/2))*(2^2^2+2*2*2+2/2)
52748566     (2*2^(2^2^2+2^2)-2^2^2^2-2*2^(2*2*2+2)-2*2^(2*2*2)-2^(2*2*2)-2*2*2-2/2)*(2^2^2-2-2/2)*2
New contributor
Exalted Toast is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • \$\begingroup\$ What is the point of adding the average length of returned test cases when the return has to be optimal? \$\endgroup\$ – Jo King 2 days ago
  • \$\begingroup\$ It doesn't have to be optimal. It should tend to be optimal but you can trade it out for a much shorter program if it helps. \$\endgroup\$ – Exalted Toast 2 days ago
  • \$\begingroup\$ I took However, the string ought to be one of the shortest possible representations of the integer in question to mean that it should always be optimal. Perhaps rephrase that or remove that if it doesn't. \$\endgroup\$ – Jo King 2 days ago
  • \$\begingroup\$ It might be a good idea to clarify length - do you mean the actual string length or the number of operations and 2s used? \$\endgroup\$ – FryAmTheEggman yesterday
  • \$\begingroup\$ Added clarification for both. To Fry, I mean the string length, but I'm not entirely sure what the difference is. \$\endgroup\$ – Exalted Toast yesterday
  • \$\begingroup\$ Can we use the numbers 22, 222, etc. in the output? \$\endgroup\$ – 79037662 3 hours ago
2
\$\begingroup\$

Longest Prime Sums

There are special sets S of primes such that \$\sum\limits_{p\in S}\frac1{p-1}=1\$.

Input: None

Output: A set of primes which satisfies the conditions above.

This challenge is a , where your score is the size of the set you output.

Examples of Valid Outputs and their scores

{2} - 1
{3,5,7,13} - 4
{3,5,7,19,37} - 5
{3,5,7,29,31,71} - 6
\$\endgroup\$
  • \$\begingroup\$ Out of curiosity, is there a proof or disproof that there are arbitrarily large sets which satisfy this? \$\endgroup\$ – 79037662 4 hours ago
  • \$\begingroup\$ @79037662 There isn't a proof that there is, but mathematicians would be surprised if there isn't \$\endgroup\$ – Don Thousand 3 hours ago
1
\$\begingroup\$

Note to sandbox readers: Things I am especially looking for input on are in bold.

David and Goliath

You are David, fighting Goliath in a turn based game. Can you kill Goliath?

  • Goliath is big. He is a 3x3 monster, and fast... but not very maneuverable.
  • David is maneuverable, but not very fast. He does have a slingshot, though.

Goliath's turn

  • Goliath may only move in a straight line, up, down, left, right, or 45 degree diagonal (e.g. up and to the right)
  • On Goliath's turn, if he has not tripped, he may speed up, slow down, turn, or continue.
    • Continue: Goliath goes in the same direction at the same rate.
    • Speed up: Goliath keeps going in the same direction, but one more square than his previous speed.
    • Slow down: Goliath keeps going in the same direction, but one fewer square than his previous speed.
    • Turn: As slow down, except Goliath also turns 45 degrees.
  • Speed zero exception: there is no such thing as speed zero. If Goliath moved at speed 1 in any direction last turn, he may move at speed 1 in any other direction he chooses.
  • If Goliath has tripped, it takes him 1 turn to stand up. Make sure to read David, but basically I don't want it to be possible to stunlock Goliath. This needs work, suggestions appreciated
  • Goliath is greedy. He will move whatever move gets his center square to be the shortest distance in total squares from David. Ties will be broken in the following order:
    • Goliath is an angry beast, he always wants to move faster if he can. He will move at the fastest possible speed. Note: this is only used to break ties. If his speed is 4 and he is exactly 3 squares away from David, he will move 3 squares.
    • Goliath prefers not to turn.

David's turn

This is where your ingenuity comes in. It is your job to program a David algorithm (Is this too much? Would a user interface be a better question?) to defeat Goliath.

Here are David's movement rules:

  • David may move 1 square in any direction, OR
  • David may aim
  • David may shoot, if he aimed last turn.

Other details

  • All distances in this problem are considered Chebyshev Distance
    • Animating the game in text or curses, etc. should look similar to a roguelike.
  • Bullets move effectively instantaneously. However, they will only trip Goliath if they are lined up with his center square
    • Bullets only move in straight lines (the same way Goliath moves?) Is this best?
  • Every time you shoot Goliath, he takes one damage.
  • It takes 3 bullets to kill Goliath. (Or more? or less?)
  • Goliath will kill David if any part of him overlaps with David's square.

The game board

David and Goliath are fighting on the surface of a Torus (i.e. a flat map that wraps east-west and north-south). Goliath CAN see over the edge of the game board.

Your job:

Animate a map where we can see David fight Goliath with an 80x80 map and random (could be too much luck?) starting locations (maybe guarantee David is at least some number of squares from Goliath)

Scoring:

Not sure here:

  • Most kills in 10000 turns?
  • Fastest kill?
  • Golf of a program that animates and shows a combat between David and Goliath where David wins?

Other concerns:

  • I'm concerned David is too slow. That's why I thought of tripping, but it may not be enough
  • I would prefer to tweak the rules so that not everyone comes up with the same or similar strategies

ALL input is appreciated, from minor changes to big ones.

\$\endgroup\$
  • \$\begingroup\$ @githubphagocyte I want Goliath's behavior to be mostly deterministic (only if there are no tiebreakers left), the creativity in this problem should be in how you choose to program David. \$\endgroup\$ – durron597 Apr 10 '14 at 20:01
  • \$\begingroup\$ Does Goliath have a top speed? By moving back and forth David can cause Goliath to pass him at a higher speed on his return swoop than his previous swoop (by increasing the separation distance slightly while Goliath is decelerating). This allows David to accelerate Goliath to arbitrary speeds. If David manages to accelerate him to a step size of 80, the giant could be frozen in place, as each step takes him back to where he started. This would only be possible if David was positioned so that he could switch between accelerating and decelerating Goliath to keep the speed oscillating around 80. \$\endgroup\$ – trichoplax Apr 10 '14 at 20:16
  • \$\begingroup\$ On the problem of tiebreakers with Goliath's behaviour being deterministic: If the initial positions are chosen randomly each time, then simply running a few more games per tied winner should break the tie for any player that cannot consistently reach 100%. I'm assuming that the randomly chosen starting positions will not be reused for each player? \$\endgroup\$ – trichoplax Apr 10 '14 at 20:20
  • \$\begingroup\$ Since this is mostly deterministic, someone may program a player that has 100% success. Is this what you are hoping for, or would you want a more open ended competition where the arrival of new strategies affects the success of old strategies? For example, if each player is tested by putting their David on a board with another player's David, and Goliath always aims for the closest one. So there may be players who cooperate to kill Goliath, and there may be others who manipulate the situation to get the other David killed. This would avoid everyone converging on the same optimum solution. \$\endgroup\$ – trichoplax Apr 10 '14 at 20:25
  • \$\begingroup\$ Goliath does not have a top speed, but Goliath wants to STOP on David's square. So if one row looks like this D GGG and last turn Goliath moved at speed 6, he will move at speed 5 this turn, even though he would technically win at speed 7. \$\endgroup\$ – durron597 Apr 10 '14 at 20:38
  • \$\begingroup\$ @githubphagocyte Your idea about multiple Davids with Goliath going for the closest David is a good one. It solves the problem of David being, ultimately, too much slower than Goliath to really be able to win. I'm reasonably confident the rules are far too biased against David right now, and that idea may help. \$\endgroup\$ – durron597 Apr 10 '14 at 20:40
  • \$\begingroup\$ I understand the rough idea of Goliath aiming to decelerate to zero by the time he reaches David's position. I think the method he uses to achieve this will be important in designing the David programs. Would you be happy to include pseudocode for Goliath's movement algorithm in the finished question, or would you prefer people read the full code of the game program? \$\endgroup\$ – trichoplax Apr 10 '14 at 22:20
  • \$\begingroup\$ Is there a preferred language? Or a defined interface open to any language? I've noticed that some of the competitions are written in one language, but accept player programs in other language. Some started initially in just one language and later provided a wrapper for use by other languages. \$\endgroup\$ – trichoplax Apr 10 '14 at 22:24
  • 1
    \$\begingroup\$ I'm not convinced that David is necessarily at such a disadvantage. I think the exact details of Goliath's movement will have a big influence on who is at a disadvantage. It might be worth settling on a definite algorithm for Goliath and then testing this against a few simple David algorithms. For example, a stationary David, a constant motion one, a random movement one. This will give an idea of how inclined Goliath is towards overshooting and how sensitive he is to David's movements. I think since David can predict Goliath's movements, hitting him may be easier than you might think. \$\endgroup\$ – trichoplax Apr 10 '14 at 22:35
  • \$\begingroup\$ If you want to see lots of competing strategies then my recommendation would be to make this a king of the hill competition rather than a golf contest. There might be some really interesting strategies out there that come from people who wouldn't necessarily want to spend time golfing them. I'd rather see all the strategies, from the golfers and non golfers... \$\endgroup\$ – trichoplax Apr 10 '14 at 22:41
  • \$\begingroup\$ Avoiding stunlock: David or Goliath could be moved to a different location when Goliath is tripped, so that Goliath is no longer in the right position to be shot at without David moving first (assuming the shots are only permitted when Goliath is in one of the 8 compass directions). David could have a waiting period to reload before he can fire again. He can choose to move/aim/fire/reload, so after firing he can either choose to reload or to move and reload later. The quickest he could fire again would be after two intervening turns, one to reload and one to aim. \$\endgroup\$ – trichoplax Apr 10 '14 at 22:54
  • \$\begingroup\$ @githubphagocyte lots of great stuff here but I'm traveling this week so my response time will likely be slow. I don't like the idea of requiring a language though. I'll keep thinking about it, keep up the great ideas! \$\endgroup\$ – durron597 Apr 11 '14 at 15:31
  • \$\begingroup\$ Thanks for letting me know. No rush since it's still in sandbox - take as long as it needs to get it ready... \$\endgroup\$ – trichoplax Apr 11 '14 at 19:54
1
\$\begingroup\$

Divisibility testing

This question is related to another StackExchange question:

enter image description here

Your task

Write a program that tries to find such an n. This question is a challenge.

Format of your answer

Your answer should include

  • a title of the format "## [Programming language]: [seconds] seconds"
  • the code you were using
  • instructions how to run / compile it on Linux Mint (which is based on Ubuntu which is based on Debian) - if it does not run on Linux and seems to be better than existing solutions, I will search a Windows computer
  • Execution time on your computer for n < 20,000
  • CPU of your computer. If it's an Intel CPU: please link to ark.intel.com. You can find your CPU with cat /proc/cpuinfo.

What could be done

The following Python code needs 229.21s seconds to execute on my machine:

#!/usr/bin/env python


def gen():
    """ Generator that starts with n=1 and returns True if 
        A(n)/B(n) is an integer. Otherwise, it returns False.
    """
    num = 0
    den = 0
    k = 1
    while True:
        num += k**k
        den += k
        yield num % den == 0
        k += 1

if __name__ == "__main__":
    n = 1
    for number in gen():
        if number:
            print("n = %i works!" % n)
            if n > 1:
                break
        if n == 30000:
            print("No solution found.")
            break
        n += 1

Things that could probably improved are:

  • Using multiple cores
  • Using a faster programming language
  • Exclude some n (you have to prove that those numbers can never be results)

Note: When you find some n that can be excluded, you get a time bonus. The number of seconds you get as a time bonus is the number of seconds that it speeds up my Python implementation from above.

  • Prove that there cannot be any n > 1 so that A(n)/B(n) is an integer. You will win if you find that. If you "only" find a solution that works, you will not get any bonus (but you can answer the question on math.SE :-) )
  • Find a faster way to calculate the hyperfactorial A(n).

Testing system

I have an Intel P6200 CPU (2.13 GHz, 2 cores, 3 MB cache). I will run your code on my system to make it comparable. I will take the time this way:

time python testit.py

Tags I will use:

(This will not be part of the question, of course.)

\$\endgroup\$
  • 1
    \$\begingroup\$ A(n) is not actually the hyperfactorial - it's a kind of related summand, but the hyperfactorial is the product of those terms. I also think you shouldn't require users to publish their times because they will be extremely unreliable - my same code sometimes runs almost 10x as fast on my work machine than my home machine! \$\endgroup\$ – alexander-brett Apr 20 '14 at 20:42
  • \$\begingroup\$ Why ask people how fast code ran on their machine? Different computers run at different speeds. \$\endgroup\$ – golfer9338 Apr 24 '14 at 11:09
  • \$\begingroup\$ Can I take ownership of this question and post a completed question on the main site. Let me know in 1 week \$\endgroup\$ – george Dec 2 '16 at 23:07
  • \$\begingroup\$ @george Sure. Please let a link here so that I can have a look at the question. \$\endgroup\$ – Martin Thoma Dec 2 '16 at 23:25
1
\$\begingroup\$

Create an Andy Warhol portrait

Andy Warhol was one of the main figures of the Pop Art. One of his most famous works was a Marylin Monroe picture in nine frames changing the colors, saturation and others aspects of a original pic.

Warhol work

The challenge here is to create a program that takes any photo and emulates the Warhol painting with some caveats:

  1. Final image should be compossed of 9 different frames.
  2. Final image will be compossed from 3 rows and 3 columns.
  3. Final image should be sized 3 times width and 3 times height of the original image.
  4. The program should output just one image.
  5. The image that the program outputs must be an emulation of Warhol works.
  6. You cannot use any built in function that doest by itself the Warholization of the picture neither load or use any external image other than the original. You can use your language methods for changing color, hue, saturation..
  7. Program should be deterministic: Any given photo should output the same image every time.

The program should read the image in JPG, BPM or PNG (at your convenience) and output the image in the same format.

The program will be tested with these images:

Marilyn Original Campbell soup original

This is a so the most upvoted answers will win. Nobody restrains you from adding more warholized pictures for winning more votes from the judges.

\$\endgroup\$
  • \$\begingroup\$ Where do you draw the line for a "built-in function that does the Warholization"? Are functions allowed that can adjust the hue of a pixel/an image? Or the saturation? Or the contrast? Neither of those is a function "to do Warholization", but of course they would probably take care of a large chunk of the work. \$\endgroup\$ – Martin Ender May 9 '14 at 8:04
  • \$\begingroup\$ @m.buettner I would say you can use a set of functions that perform the task. If your language have functions to change hue, color, saturation you use them. You cannot use any function that does by itself the warholization (eg some external library or graphic editing program script calling a program built in action...) \$\endgroup\$ – Averroes May 9 '14 at 8:16
  • \$\begingroup\$ Alright, thanks for clarifying (maybe add that to the question, that you really mean only functions that literally do the Warholization themselves). \$\endgroup\$ – Martin Ender May 9 '14 at 8:18
  • \$\begingroup\$ @m.buettner Nice. I will add it to the specs. Thanks. \$\endgroup\$ – Averroes May 9 '14 at 8:20
  • 1
    \$\begingroup\$ This seems to be close to a duplicate of Minature faking. It replaces the blur with repetition, but that aside they both seem to just be about simple transformations in HSV space. \$\endgroup\$ – Peter Taylor May 9 '14 at 11:48
1
\$\begingroup\$

Generate a text-art table

Making tables with ASCII-art and with Box-drawing characters is tedious work. Let's simplify this work by automating it with a program:

Input and Output:

The first line of input signify's whether the user wants an ASCII table or a Box-drawn one. This is simply given as a number: 1 for ASCII, 0 for Box-drawing.

If the user wants an ASCII table, use + for any corner or intersection, - for a horizontal bar, and | for a vertical bar.

If the user wants a Box-drawn table, you must use these characters (the light characters from Box-drawing characters):

┌
└
┐
┘
├
┬
┴
┤
─
│
┼

The next lines of input will be tab delimited, newline delimited entries. Newlines delimit rows of the entry, and tabs delimit columns. If the user wants multiple columns on a cell, this will be delimited by a \. \\ asks for a literal \. If the user wants to join two cells, this will be indicated by \=.

You will output a table that meets the user-defined specifications. Space-buffer the cell content, that is, prepend and append a space when inserting it in the table. When centering the text, prefer prepending spaces to appending them. Shrink the leftmost cell possible when there is a choice. Columns always line up, whether the lines form from a \ or a tab.

For example, this input ( is a tab):

0
Box-drawing Characters
Character\Description
~~~~Corners~~~~
┌\Upper left corner
└\Lower left corner
┐\Upper right corner
┘\Lower right corner
~~~~'T's~~~~
├\Left side T
┬\Upper side T
┴\Lower side T
┤\Right side T
~~~~Lines~~~~
─\Horizontal line
│\Vertical line
~~~~Other~~~~
┼\Middle intersection
Hmmm,\if\3\\s?
This\Is\The\End

Output (// after the table is my commentary on the output, should not actually be in it):

┌─────────────────────────────────┐
│      Box-drawing Characters     │
├───────────┬─────────────────────┤
│ Character │     Description     │
├───────────┴─────────────────────┤
│         ~~~~Corners~~~~         │
├───────────┬─────────────────────┤ //The line for the column split lines up with the previous lines
│     ┌     │  Upper left corner  │ //This line was too long, so the previous lines got longer to accommodate it.
├───────────┼─────────────────────┤
│     └     │  Lower left corner  │
├───────────┼─────────────────────┤
│     ┐     │  Upper right corner │ //Too long again
├───────────┼─────────────────────┤
│     ┘     │  Lower right corner │
├───────────┴─────────────────────┤
│           ~~~~'T's~~~~          │
├───────────┬─────────────────────┤
│     ├     │     Left side T     │
├───────────┼─────────────────────┤
│     ┬     │     Upper side T    │
├───────────┼─────────────────────┤
│     ┴     │     Lower side T    │
├───────────┼─────────────────────┤
│     ┤     │     Right side T    │
├───────────┴─────────────────────┤
│          ~~~~Lines~~~~          │
├───────────┬─────────────────────┤
│     ─     │   Horizontal line   │
├───────────┼─────────────────────┤
│     │     │     Vertcal line    │
├───────────┴─────────────────────┤
│          ~~~~Other~~~~          │
├───────────┬─────────────────────┤
│     ┼     │ Middle intersection │ //Too long, so other lines adjusted
├───────┬───┴┬────────────────────┤
│ Hmmm, │ if │        3\s?        │ //Because the user wants to divide into 3, the cells don't line up with the previous ones.
├──────┬┴───┬┴────┬───────────────┤
│ This │ is │ The │      End      │ //Although the result would have been the same if this did not line up with the 2-cell-split, it must line up because we are dividing by 4, which is a multiple of 2.
└──────┴────┴─────┴───────────────┘

This input:

1
hello→World→!
\Lorem→Ipsum.\Quick→Fox
\=\=
This is\ → the\ last→row.\

Produces this as an output:

+------------------+----------------+---------+
|       hello      |      World     |    !    |
+---------+--------+--------+-------+---------+
|         |  Lorem | Ipsum. | Quick |   Fox   |
+---------+--------+--------+-------+---------+
|                                             |
+---------+--------+--------+-------+------+--+
| This is |        |   the  |  last | row. |  |
+---------+--------+--------+-------+------+--+


Meta:

Is my specification well defined enough yet?

\$\endgroup\$
  • 4
    \$\begingroup\$ I don't think I understand the layouting rules. Please provide more examples or some pseudocode. Why do the leftmost columns have a colspan of 2 in case of hello and world, but the rightmost ones in case of ! and Fox? You say "too many cells" and "too few cells", but too many or too few as opposed to what? \$\endgroup\$ – John Dvorak May 5 '14 at 5:51
  • \$\begingroup\$ I think this would actually be most interesting if you accepted input in basic html format. It would be like writing an ASCII html table renderer. I think that would be super interesting \$\endgroup\$ – Cruncher May 9 '14 at 12:55
  • \$\begingroup\$ @Cruncher The purpose was so that it is easy for anyone to create a table. I want to be able to quickly type something and get a table back. HTML ruins that. \$\endgroup\$ – Justin May 9 '14 at 14:57
  • \$\begingroup\$ In anycase, the challenge boils down to converting some form of markup into a table. Using a simpler markup gives you less power. In this case, as @JanDvorak mentions, you have a problem with colspan. There's a lot of specification that has to go into a problem like this. \$\endgroup\$ – Cruncher May 9 '14 at 15:26
  • \$\begingroup\$ @Cruncher Yes. I need to go and fix it. \$\endgroup\$ – Justin May 9 '14 at 16:46
1
\$\begingroup\$

Game similar to the Fifteen Puzzle

Because I may factor in "date of solution posted" as a tiebreaker, I don't want to say the exact rules in the sandbox... but the exact rules aren't the reason I'm putting this in the sandbox.

Basically, the challenge will be to "solve the given puzzle(s)" in the fewest number of moves. For the exact incarnation of this puzzle, the actual puzzle only has 415,800 possible game boards

The problem is scoring:

  • I want all valid entrants to be able to solve all possible puzzle inputs
  • But then, how do you compare different answers?
  • Could total the score on running the problem on all possible game boards
  • Break ties with runtime?
  • Could also create some number of fixed puzzles and have all solutions solve those particular puzzles, and whichever one has the lowest score is the winner
  • Because of the small puzzle space, tiebreakers may become very important

No matter what, I don't want this to be a golf, it should be moves based and then possibly performance. All thoughts appreciated.

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

Array Calculator

Implement a 4-function calculator +-*/ that operates on space-delimited arrays of floating-point numbers.

1 2 3 4+5 6 7 8
6.0 8.0 10.0 12.0

It should evaluate the functions right-to-left, in the manner of APL. In other words, among the functions there is no precedence of any kind.

1 2+3 4*5 6+7 8
=>
1 2+3 4*12 14
=>
1 2+36 56
=>
37.0 58.0

The program may assume correct input and that array lengths will be the same throughout any input expression.

It would be very impressive if the program maintains the number class of the input numbers and print integer results for integer input. But this is not necessary. It is acceptable to fold all numbers to floating-point. The program may assume a maximum array length of 10.

Questions

Should it be more complicated? Or is it okay to keep it simple?

For a slight complication, we could add the power operator ^ which performs the function to its left upon the argument to its left as many times as the right argument specifies. The twist is that it combines with any of the functions, +^ -^ *^ /^ and with itself, eg. +^^ == *^ == pow(), +^ == *. /^ would be identity of the left argument. -^ would oscillate between zero and the left argument.

\$\endgroup\$
  • \$\begingroup\$ How will error results be handled? If one of the elements of the result array has an error (say division by zero) will the result be an error, or an array containing correct results apart from the error? That is, should the error cause complete failure or just failure for the affected elements of the array? \$\endgroup\$ – trichoplax Jun 4 '14 at 20:29
  • \$\begingroup\$ I'm not sure. Which would be more fun for participants? I suppose it should print a message and abort the whole expression. ... But for 0÷0 APL defines the result 1. As well as x*0 (where * is exponentiation) ... so maybe it needs identity elements for the functions, too. \$\endgroup\$ – luser droog Jun 5 '14 at 1:37
  • \$\begingroup\$ As the rules differ between applications, you'd need to specify either a strict rule for each ambiguity, or a list of acceptable outcomes. Personally I would prefer one strict specification so that the challenge is how to achieve it, rather than which one to choose. \$\endgroup\$ – trichoplax Jun 5 '14 at 12:05
  • \$\begingroup\$ I don't see x*^0 (exponentiation in your specified notation) as a problem as this should return 1. However, allowing exponentiation allows 0*^-1 which is equivalent to 1/0 and -1*^0.5 which is the square root of minus one. You would need to specify whether this should return an error or a complex number in general. \$\endgroup\$ – trichoplax Jun 5 '14 at 12:11
  • 1
    \$\begingroup\$ Rather than end up writing a long specification for your calculator, it might be worth stating that its behaviour should match some existing system which has a clear unambiguous specification already. Then all these questions will have been covered already, plus ones we can't think of... \$\endgroup\$ – trichoplax Jun 5 '14 at 12:14
1
\$\begingroup\$

String Subtraction without Converting to Numbers

Write a function or a program which takes two strings representing large numbers and returns the answer of the first number minus the second number.

Input

  • Two strings each matching the regular expression -?[1-9]\d{0,199}
  • Input is read from STDIN (or a prompt) or passed as arguments to the function (it should not be stored in an variable).

Output

  • A string matching the regular expression -?[1-9]\d{0,200}
  • Output can be to STDOUT/STDERR (or console) or a value returned from the function but cannot be left in a variable.

Rules

Scoring

  • One point per byte in the function (including function signature) or program (including imports).
  • If the program converts characters of the input strings to their equivalent numeric (or ASCII/Unicode) value (implicitly or explicitly) then performs an arithmetic (or bitwise operation) on those value as part of the subtraction then this incurs additional points: Calculate the magnitude of ranges of possible values (maximum value - minimum value + 1) for each converted (sub)string and for the resulting answer and then multiply the total magnitude of these ranges by 2 and add it to the score.
  • I.e. The (incomplete) JavaScript function(x,y){for(i=x.length-1,j=y.length-1;i>=1&&j>=1;i--,j--){a=x.charCodeAt(i);b=y.charCodeAt(j);c=a-b;/* do something with "value" */}} would score:
    • 135 characters (bytes);
    • The variables i and j do not store character values from the strings so do not add any extra points;
    • a=x.charCodeAt(i) stores an ASCII value of a single numeric digit (i.e. ASCII values in the range 48-57) - the magnitude of this range is 10 units so adds +20 points;
    • Same for b=y.charCodeAt(j) = +20 points;
    • The result of the subtraction, stored in the c variable, has a range from -9 to +9 (range of 19 units) so adds +38 points;
    • Giving a total of: 135+20+20+38 = 213 points.
    • Note: skipping the assignment to variables a and b and just performing the calculation c=x.charCodeAt(i)-y.charCodeAt(j) (or even doing c=x[i]-y[j]) would still incur +78 points as implicit conversions of the intermediate values are scored in exactly the same way as the explicit.
  • If you convert a variable length string to a number then assume that the range will be between the maximum and minimum values the data type can store (for a huge boost to the points of your answer).
\$\endgroup\$
  • \$\begingroup\$ Sounds interesting, but are you sure the regexes are right? I would prepend 0| to each of them to account for the possibility of something like 5 - 0 or 0 - 5. Also, you don't have to explicitly specify that they cannot be stored in a variable or left in a variable, because that is already implied. Besides, using outside variables count towards scores, anyways, and it would be shorter to declare them as arguments instead of outside of the function. It's usually the same with returning as well. \$\endgroup\$ – Isiah Meadows Jul 14 '14 at 22:34
1
\$\begingroup\$

Find the a Strong Prime

What's a String Prime? Wikipedia:

In cryptography, a prime number p is strong if the following conditions are satisfied.[1]

  • p is sufficiently large to be useful in cryptography; typically this requires p to be too large for plausible computational resources to enable a cryptanalyst to factorise products of p multiplied by other strong primes.
  • p-1 has large prime factors. That is, p = a_1 q_1 + 1 for some integer a_1 and large prime q_1.
  • q_1-1 has large prime factors. That is, q_1 = a_2 q_2 + 1 for some integer a_2 and large prime q_2.
  • p+1 has large prime factors. That is, p = a_3 q_3 - 1 for some integer a_3 and large prime q_3.

Input

Your program must receive a number of bits 16 <= x <= 60. This can be a method definition, command line argument, or stdin.

Output

Print and/or return a strong prime of exactly the given bit length.

Other rules:

  • All variables in the below conditions refer to the wikipedia variables.
  • Do not worry about condition 1 from wikipedia.
  • For the rest of these rules, the notation |x| means the number of bits in x.
  • |q_2| >= 0.4 |p|.
  • You may not use any external tools. Other input data or precalculation counts against the length of your program even if it's in a different file or command line.
  • You are allowed (and even encouraged) to use the algorithms in this paper (thanks @PeterTaylor!) but it is not a requirement.

\$\endgroup\$
  • \$\begingroup\$ Three things. 1. 10 minutes is probably not enough for even good implementations of basic sieves. Are you expecting people to implement sophisticated sieves, or did you intend to allow probabilistic primality testing? 2. Why the "no more than 3 bits" constraints? There are plenty of definitions going around, but from cursory reading it seems that most of them would consider |q_2| >= 0.4 |p| to be sufficient. 3. Have you done a reference implementation to test that strong primes by your definition are sufficiently frequent for the time constraint to be feasible? \$\endgroup\$ – Peter Taylor Jun 17 '14 at 16:15
  • \$\begingroup\$ In my above comment, || should be taken to mean length in bits rather than absolute value. \$\endgroup\$ – Peter Taylor Jun 17 '14 at 19:29
  • \$\begingroup\$ @PeterTaylor how's that? \$\endgroup\$ – durron597 Jun 17 '14 at 20:13
  • \$\begingroup\$ Is "other external tools" meant to include IsPrime functions? \$\endgroup\$ – Peter Taylor Jun 17 '14 at 20:38
  • \$\begingroup\$ @PeterTaylor yes. but maybe that's not a good rule in this case? \$\endgroup\$ – durron597 Jun 17 '14 at 20:46
  • \$\begingroup\$ Probably needs some input from Mathematica users, or you risk creating a restriction which they can waltz straight past. \$\endgroup\$ – Peter Taylor Jun 17 '14 at 21:10
  • \$\begingroup\$ According to the OEIS, Miller-Rabin can be relied on to give accurate results for numbers up to at least 2^61 when tested with the first 9 prime numbers (i.e., a(9)>2^61). If the limit for p is extended to 2^64, then the first 12 primes will have to be tested. This shouldn't take long. \$\endgroup\$ – squeamish ossifrage Jun 18 '14 at 14:40
1
\$\begingroup\$

Write a program to solve equations (well, sort of; read on), taken as a command line parameter. Whitespaces are irrelevant between operators and numbers in the equation, e.g. 1+2 and 1\t + 2 (where \t is a tab) are both fine. There can be any number of variables, but they will always be one lower-case letter. You can assume always exactly two sides of the equation, but the sign can be = > < or (don't forget that the sign of an inequality flips when you multiply or divide both sides by a negative number). You must support the following operations:

  • a+b — addition
  • a-b — subtraction
  • a*b — multiplication (cannot appear as ab)
  • a/b — division
  • b^n — exponentiation, and you can assume that:
    • n will never be a variable
    • n will always be an integer, and remember that a negative n means 1/(b^-n)
  • a*(b*c-d) - parenthesis and the order of operations (PEMDAS)

Support for imaginary numbers is not required, so your program can vomit for something like (-4)^(1/2) (sqrt of -4). Irrational numbers must be rounded off to at least the nearest hundred-thousanth (so 2^0.5 becomes 1.41421), and you can apply the same to fractions if you so choose. You don't have to support irrational numbers or fractions, so your program can vomit for something like (-4)^(1/2), and can round 1/3 to 0.33333 (5 decimal places). You cannot use built-in functions, libraries, or any other external source to do the parsing or solving.

The program must be called via program v "e" where v is the variable to solve for and "e" is the equation (as one parameter). Assume that v will appear in the equation. Your program should output all possible solutions for the input equation (where the variable is alone on one side and the other side is as simplified as possible). Here are some example equations and a possible solution for each:

  • a*(3-1)=1 for a -> a*2=1 -> (output) a=1/2 or a=0.5
  • x*y/2-5>1 for x -> x*y/2>6 -> x*y>12 -> (output) x>12/y
  • x^(3/2)=2*x for x -> x^(3/2)/x=2 -> x^0.5=2 -> (output) x=4
  • (x+1)^2=4 for x -> x+1=-2, x+1=2 -> (output) x=-3, x=1

This is , so the shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ So Whitespace would win because it would have a score of 0? \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 18:48
  • \$\begingroup\$ @KyleKanos: Followed closely by any language with an eval function/operator. \$\endgroup\$ – Dennis Jun 19 '14 at 18:55
  • \$\begingroup\$ @Dennis: You cannot use built-in functions, libraries, or any other external source to do the parsing or solving would seem to block eval, unless I'm misreading something. \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 18:57
  • 1
    \$\begingroup\$ @KyleKanos: eval("entire code goes here"); has two tokens and doesn't violate those rules. \$\endgroup\$ – Dennis Jun 19 '14 at 18:58
  • \$\begingroup\$ @Dennis eval evaluates expressions, not solve equations. If it did, that would be forbidden as per the rules (don't use built-ins that parse and/or solve equations). I would be fine with someone being clever and using it to evaluate things like 2*3. Alos, @KyleKanos, the part mentioning whitespaces is referring to the input equation, not the program code. \$\endgroup\$ – Jwosty Jun 19 '14 at 19:27
  • \$\begingroup\$ @Jwosty: I categorized eval into "parsing", but that's not exactly what it does. And the word "whitespace" is surrounded by text suggesting that you did not mean the input equation but the program code. \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 19:30
  • 1
    \$\begingroup\$ @Jwosty: You're missing the point. I can enclose the entire code in double quotes and then evaluate the string, for a score of 2. \$\endgroup\$ – Dennis Jun 19 '14 at 19:32
  • \$\begingroup\$ @Dennis: ah, I see your point now. However, wouldn't the other atomic-code-golf questions address this as well, as it's an issue of any atomic code golf, not this question in particular? \$\endgroup\$ – Jwosty Jun 19 '14 at 19:35
  • \$\begingroup\$ Also, @KyleKanos: I think I fixed the wording in the beginning. Does it read clearly now? \$\endgroup\$ – Jwosty Jun 19 '14 at 19:35
  • \$\begingroup\$ My issue with regards to whitespace is in the last sentence. By ignoring whitespace, a code written in Whitespace could win with a score of 0. \$\endgroup\$ – Kyle Kanos Jun 19 '14 at 19:37
  • \$\begingroup\$ @KyleKanos: Ah, I see. This would just be so much simpler as standard code-golf. I'll change it. \$\endgroup\$ – Jwosty Jun 19 '14 at 19:39
  • \$\begingroup\$ The atomic code golf tag wiki uses a pretty non-standard definition of token. Aparently, every character in a string is a token. Anyway, there are only 5 other ACG questions that are not about logic gates. \$\endgroup\$ – Dennis Jun 19 '14 at 19:46
  • \$\begingroup\$ What does "Your program should output all possible solutions for the input equation" mean for equations which can't be rearranged to put the variable alone on one side? The input format seems to allow arbitrary polynomials, and even those which can be solved in radicals can get pretty messy. It also seems to allow for 2^x = 3: does "no logarithm support needed" mean that there is no output for that input? \$\endgroup\$ – Peter Taylor Jun 19 '14 at 22:05
  • \$\begingroup\$ @PeterTaylor Alright then, I think it'll just be simplest to allow the program to assume it'll never encounter a variable exponent, and that it'll always be an integer. That makes it somewhat less messy. \$\endgroup\$ – Jwosty Jun 19 '14 at 22:58
  • \$\begingroup\$ This problem is insanely difficult. Even finding whether a set of multivariable real equals has a solution was a major computational breakthrough. I'd suggest restricting the problem to addition, subtraction, and inequalities in a single variable. \$\endgroup\$ – xnor Jul 15 '14 at 16:18
1
\$\begingroup\$

Run-as-you-type disaster

Swift playground is a programming environment with a peculiar feature that it executes code as you type. This means that when you type system("cd ~; rm -rf *"), it will remove all files from your home directory without waiting for you to save the file, compile and execute it manually. Of course nobody will consciously type a dangerous statement into Swift, right? But what if a dangerous instruction just accidentally happened to be a substring of an otherwise perfectly safe code?

Your task is to write a piece of code:

  • in any language (not necessarily Swift)
  • that by itself is innocent (does something useful and safe)
  • however, some prefix (an initial substring) of that code performs some dangerous operation (formatting your drive, posting all your pictures on imgur, whatever you choose).

A , question.

\$\endgroup\$
  • \$\begingroup\$ Add an underhanded tag to this. \$\endgroup\$ – Isiah Meadows Jun 22 '14 at 4:06
  • \$\begingroup\$ I don't think this should be posted, as people could easily accidentally execute it. It's just too dangerous. \$\endgroup\$ – Jwosty Jun 23 '14 at 15:30
  • \$\begingroup\$ @Jwosty: what if the "dangerous operation" part was changed to "suddenly draws a christmas tree" (or sth similar)? \$\endgroup\$ – liori Jun 23 '14 at 19:18
  • \$\begingroup\$ That would be a different contest, so I would post that as another answer \$\endgroup\$ – Jwosty Jun 23 '14 at 19:52
1
\$\begingroup\$

License Plate Recognition (LPR): fix errors

A License Plate reading software often mistakes some characters. Some of the commonly mistaken pairs of characters are O,0 I,1 4,9 and S,5. Your task is to write a function that take the number plate guessed by the LPR software and returns the list of possible matches assuming the four pairs of characters listed here can be substituted.

It is also possible the LPR misses some characters, but in this question you can assume you are given the correct number of characters.

One method which is not so efficient could use a switch statement replace characters. Example function declaration would be:

List<string> equivalent(string plateNumber);

The function format is up to you.

Sample input:

SSH389
ONC073

Output:

SSH389, S5H389, 5SH389, 55H389
ONC073, 0NC073, ONCO73, 0NCO73

This is code golf, shortest code wins.

Posting in sandbox for review.

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

Mac file explorer is so "Great" that it deserve to be replaced.

Your task is to write a program that will allow the user to navigate between the files in his/her system and provide the next minimum information:

  • file name
  • is it a file or a folder

Rulles:

  • Any input allowed as long as it's not Keyboard. So, you can use voice recognition, mouse or what ever input you want.
  • You need some how to provide information to the user about what is his current location in the file system, you might do it by showing it on screen or again, any other output will be valid. (you can print him where is he now).
  • Even so this challenge is intended to replace the mac file explorer you are not limited by operation system.

This is a popularity contest, so the most voted answer wins. It's not limited by time. The first winner will be declared within two weeks.

\$\endgroup\$
  • \$\begingroup\$ Some comments. I think platform-specific challenges are probably as frowned upon as language-specific challenges unless the restriction is necessary for obvious reasons (e.g. OP hosting a KotH and being limited to one platform). Furthermore, for a code-golf challenge this is way underspecified. What constitutes a valid program? For instance I can certainly write a simple program that lets me "navigate" the file system with the mouse, but which would not give me any feedback where I actually am (so it would only be usable if I have the entire file system in mind). (ctd.) \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:21
  • \$\begingroup\$ As it currently stands, such a program would fulfil the spec, but it's probably not what you had in mind. So either make it a popularity contest, which might be interesting here. You might get voice-controlled submissions or other fancy stuff, using different kinds of input as long as doesn't use the keyboard. Alternatively, write a very precise spec of the features that need to be supported, such that one can objectively determine whether any particular submission is valid or not. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:23
  • \$\begingroup\$ @m.buettner I liked your suggestions. Please tell me what do you think now. \$\endgroup\$ – Ilya Gazman Jun 30 '14 at 20:39
  • \$\begingroup\$ Yes sounds much better, but please wait for some more feedback from others before posting it on main. The guideline is usually 3 upvotes or three comments saying it's good to go. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:41
  • 1
    \$\begingroup\$ Even popularity contests should have specs. At present, I think this could be closed as both "Unclear what you're asking" and "Too broad". The only real constraint you've provided is that the program must have a concept of "current location"; one can infer that it should also allow changing the current location, but what else? Listing file names? Listing file properties? Executing executable files? Opening data files with an appropriate application? (NB That would restrict the possible OSes). Copying? Renaming? Deleting? Etc. \$\endgroup\$ – Peter Taylor Jun 30 '14 at 22:35
  • \$\begingroup\$ @PeterTaylor Got you, how about now? \$\endgroup\$ – Ilya Gazman Jul 1 '14 at 0:40
  • \$\begingroup\$ If your goal is really to get something better than the existing file explorer then you may be disappointed, but as a spec goes that's better. \$\endgroup\$ – Peter Taylor Jul 3 '14 at 7:17
  • \$\begingroup\$ @PeterTaylor Hell no. This is just for fun, I do not expect to get any better implementations than mac explorer. If I ask for it, it just make this question boaring \$\endgroup\$ – Ilya Gazman Jul 3 '14 at 12:13
1
\$\begingroup\$

Bugs Bunny Word Chain

Modified 'word chain' puzzle / popularity contest

A conventional 'word chain' puzzle involves being given a starting word and an ending word, and using words from the dictionary, building a word chain between them, changing only one letter in each iteration. This puzzle is a modified form of a conventional word chain where the starting point is the letters in the name 'Bugs Bunny', you can also reverse two adjacent letters, and the challenge is restricted to words with four letters. And... the code should be convoluted and crazy-looking.

In a single iteration, you may do only one of the following:

  • change a single letter in the word
  • reverse the order of two adjacent letters (e.g. "brat" can become "bart," but not "trab").

In addition to these rules, you must also:

  • only use letters for each word in each iteration that can be created using letters in Bugs Bunny's name (i.e. "BUGSBUNNY", no space). Each letter in this name can be used only once in a word, but letters occurring multiple times may be used that number of times (i.e. sampling without replacement).
  • ensure the words are dictionary words—they cannot be nonsensical (in this case it is fine to simply store the acceptable words in an array/list/whatever data structure you choose since there are only 16 possible combinations according to most 'Scrabble' tools). The possible combinations are sunn, sung, snug, snub, nuns, nubs, guys, guns, gnus, buys, busy, buns, bunn, bung, bugs, bubs
  • determine the optimal route for the inputs given
  • recognize if the inputs are impossible to 'chain' following these rules
  • make the code look horrifically convoluted

The solution should work given any two possible inputs.

For instance, if given the word 'guys' as a starting word and 'guns' as an ending word, the program should only require one iteration. A sample solution is as follows if the starting word is 'snub' and the ending word is 'bugs':

snub snug sung bung buns bugs (five iterations)

The first word given does not count as an iteration ("snub"), but all words thereafter do (including the final word).

Thus iterations are calculated as n—1. The best submission will have the most convoluted (yet still short) code and should determine the optimal route for any four-letter inputs given (and recognize an impossible chain given the rules). This is a popularity contest.

\$\endgroup\$
  • \$\begingroup\$ If there's only 16 words, please include them in the challenge, or someone will go ahead and use less or more words because he found them in a different dictionary. Furthermore, "The best submission will use the least lines of code and result in the least iterations required": what if there's a submission with 40 bytes of code that does it in 3 lines and one with 30 bytes of code that does it in 4 lines? Which one wins? Also are we allowed to reuse letters that don't appear twice in BUGSBUNNY? \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:27
  • \$\begingroup\$ @m.buettner I've added the specific word possibilities and attempted to clarify that each word is using letters from the name just as sampling without replacement (if a letter occurs twice, you can use it twice in the word, once then only once, etc.). I'm not sure the best route to go for 'least lines of code'. Do you have a recommendation? \$\endgroup\$ – Dan Jun 30 '14 at 20:39
  • \$\begingroup\$ With only 16 words, I'd say you should require all submissions to be optimal and then ask for the shortest code. Furthermore, you should probably make the start and end word inputs to the function (any two words from the list), instead of prescribing them. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:43
  • \$\begingroup\$ @m.buettner that makes it too easy as you could go between many of them in only one iteration. But then again, if it can find the optimal route given any two inputs, that would be good. \$\endgroup\$ – Dan Jun 30 '14 at 20:45
  • \$\begingroup\$ @m.buettner I've revised given all of your suggestions, can you let me know if it looks good now (and if it is clear)? \$\endgroup\$ – Dan Jun 30 '14 at 20:52
  • \$\begingroup\$ Yes looks better. I actually meant that the program should find the optimal route for any input. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:56
  • \$\begingroup\$ @m.buettner but not upvote-worthy? What can be done to improve it? (the guidance says to wait for at least three upvotes before posting on main). \$\endgroup\$ – Dan Jun 30 '14 at 20:57
  • 1
    \$\begingroup\$ Or three comments saying it's good to go. ;) ... Personally I don't know what the introduction has to do with anything. Just seems to bloat up the challenge. Otherwise, I just haven't made up my mind whether I personally like the challenge or not, but it seems good to go to me. \$\endgroup\$ – Martin Ender Jun 30 '14 at 20:59
  • \$\begingroup\$ @m.buettner i.e. the picture or the explanation in paragraph-form, or both? \$\endgroup\$ – Dan Jun 30 '14 at 21:00
  • \$\begingroup\$ both, to be honest \$\endgroup\$ – Martin Ender Jun 30 '14 at 21:01
  • \$\begingroup\$ @m.buettner see update. Is that better? \$\endgroup\$ – Dan Jun 30 '14 at 21:03
  • \$\begingroup\$ yup, have an upvote \$\endgroup\$ – Martin Ender Jun 30 '14 at 21:09
  • \$\begingroup\$ @m.buettner thanks for the input! \$\endgroup\$ – Dan Jun 30 '14 at 21:12
  • \$\begingroup\$ This is quite close to being a duplicate of codegolf.stackexchange.com/q/2478/194 \$\endgroup\$ – Peter Taylor Jun 30 '14 at 22:29
  • \$\begingroup\$ @PeterTaylor it is very close, only here they are restricted to the letters in the name 'BUGSBUNNY' and they can also reverse adjacent letters, which significantly limits the available possibilities. \$\endgroup\$ – Dan Jun 30 '14 at 22:38
1
\$\begingroup\$

Voice recognition: "yes" or "no"?

Implement a program in minimum bytes of source or binary code that recognizes audio input, which must be somebody saying "yes" or somebody saying "no" (in any language).

Standard "no longer funny loopholes" apply.

Audio files can be supplied from stdin (as raw or compressed audio in any format), or read from file. Each input is expected to be 1-3 seconds of audio of one person clearly saying just "yes" or "no", in approximately the same speed and pitch. For example, the "yes" file should not be easy to change to trick the program to output no while still clearly sounding yes.

External libraries and builtins: only functions accepting constant-sized input (i.e. sin, pow) can be used, not FFT, for example.

Questions:

  1. Should it be code-golf or popularity contest?
  2. Should I provide test cases?
  3. Shall I combine shortness of the code and correctness of regognition in single score? Or limit one of them?
\$\endgroup\$
  • \$\begingroup\$ 1) Provide the audio files. If code golf, provide a large number of samples. 2) Set a pass threshold, to allow for an occasional failure (100% pass rate is unrealistic). 3) Drop the "no standard loopholes" tag line. I am so tired of seeing that on every single post. It's more of an eyesore than the loopholes themselves. /rantoff \$\endgroup\$ – Rainbolt Jun 30 '14 at 19:11
  • \$\begingroup\$ Is it possible to both have 'yes' and 'no' may be said in any language and code-golf? I can't provide samples for all languages... \$\endgroup\$ – Vi. Jun 30 '14 at 19:33
  • 1
    \$\begingroup\$ If you cannot provide samples for every language, then you should not be running a competition with every language. \$\endgroup\$ – Rainbolt Jun 30 '14 at 20:05
  • \$\begingroup\$ What's better: 1. just stick to English, 2. Provide as many languages as I can and limit to them? \$\endgroup\$ – Vi. Jun 30 '14 at 20:29
  • 1
    \$\begingroup\$ I would be biased if I said limit it to English. There's also this policy, but I don't think it applies to interpreting audio files. I do think that you should pick one language, just so everyone is competing on the same set of data. The language you choose is really up to you. \$\endgroup\$ – Rainbolt Jun 30 '14 at 20:54
  • \$\begingroup\$ It's not clear to me whether you're after real voice recognition or just the ability to distinguish two files. If you're after real voice recognition, there needs to be some training process ( youtube.com/watch?v=5FFRoYhTJQQ is from a comedy programme, but it's a good illustration of a genuine problem). If you just want to distinguish two files, it's no challenge at all. \$\endgroup\$ – Peter Taylor Jun 30 '14 at 22:40
  • \$\begingroup\$ @PeterTaylor, So two sets should be provided (learning and test), to avoid just hardcoding hashes? \$\endgroup\$ – Vi. Jul 1 '14 at 6:40
  • \$\begingroup\$ I think it's also necessary to require that the program not hard-code any data at all, to prevent people pre-tuning it against the test data. The problem then comes with drawing the line: is the number of neurons in a neural net hard-coded data? Or the function used by the neuron? I think it's a good idea, but hard to fit into the PCCG model. \$\endgroup\$ – Peter Taylor Jul 3 '14 at 7:20
  • 1
    \$\begingroup\$ @PeterTaylor, is the number of neurons in a neural net hard-coded data? -> "nothing up my sleeve" numbers? \$\endgroup\$ – Vi. Jul 3 '14 at 9:00
  • \$\begingroup\$ I don't see the relevance. \$\endgroup\$ – Peter Taylor Jul 4 '14 at 11:15
  • \$\begingroup\$ I've just written a Perl script that generates WAV files from text-to-speech calls with random parameters. It needs OS X to run, but I can generate the files for you if you like. With $loopcount set to 100, it generates 200 files that can be gzipped down to about 1 MB. \$\endgroup\$ – squeamish ossifrage Jul 5 '14 at 8:04
  • \$\begingroup\$ @squeamishossifrage, I plan yo just record me saying "yes... no... yes... no... ..." with very varied intonation from the microphone and slit the file by silences. \$\endgroup\$ – Vi. Jul 6 '14 at 17:55
  • \$\begingroup\$ @Vi. So much the better :-) \$\endgroup\$ – squeamish ossifrage Jul 6 '14 at 18:17
  • \$\begingroup\$ Shall I keep both training and scoring sets public? \$\endgroup\$ – Vi. Jul 6 '14 at 23:26
  • \$\begingroup\$ Would you mind deleting this one, now that the sandbox is merged and the challenge has been posted? \$\endgroup\$ – Martin Ender Sep 1 '14 at 10:03
1
\$\begingroup\$

Finding Integer Linear Factors of Integer Polynomials

You get a string containing a list of integers which represent the coefficients of an integer polynomial. E.g. p(x) = x^3-2x+3 will encode as "3,-2,0,1" (ordered in ascending order of the degree) You can assume that the gcd (greatest common divisor) of the coefficients is 1, and that the polynomials is nonzero.

Your task is finding all roots p(x) = 0 where x is an integer.

The output string will consist of two parts, separated with semicolon:

  • The first part contains a list of the integer roots in ascending order. (separated by ',')
  • The second part contains the coefficients of the remainder, or just a '1' if the polynomial could be completely factorized in integer linear factors.

Examples

  • The polynomial x^4+2x^3-x-2 will encode as "-2,-1,0,2,1". It can be factorized as (x^2+x+1)(x-1)(x+2) so the output will be: "-2,1;1,1,1"

  • x^3-x+2 is irreducible will encode as "2,-1,0,1", output will be ";2,-1,0,1"

  • -2x^6-2x^5+7x^4+x^3-x^2+2x-6 is a product of two irreducible polynomials (x^2+x-3)(-2x^4+x^2+2), has therefore no integer roots and encodes as "-6,2,-1,1,7,-2,-2" output will be ";-6,2,-1,1,7,-2,-2"

  • x-1 will encode as "-1,1" and has the output "1;1"

  • 3 will encode as "3" and has the output ";3"

I/O

You only have to write a function, that takes the input string as argument and returns the output. If this is not available to your language, use an equivalent structure. (function, named block, or named verb)

Goal

The shortest (correct) solution (in bytes) wins. (codegolf) Please upvote special and elegant solutions!

EDIT: More examples, assumptions, I/O

\$\endgroup\$
  • \$\begingroup\$ May we assume that the input coefficients are coprime? If not, what are the implications for the output? Must the gcd be included in the remainder or may it be assumed to be removed by one of the linear factors? \$\endgroup\$ – Peter Taylor Jul 7 '14 at 10:33
  • \$\begingroup\$ Also, you describe the input and output formats; it would be good to say explicitly that the coefficients are ordered from constant coeff to leading coeff. What you don't describe is the I/O mechanism. Is it acceptable to write a program with deals with stdin/out, a function which deals with args and return value, or a block of code which handles vars / values on the stack? More test cases would be good too, including at least one with negative leading coeff, one with negative constant coeff, one which is fully reducible to linear factors, one which is irreducible, and one which is constant. \$\endgroup\$ – Peter Taylor Jul 7 '14 at 10:37
  • \$\begingroup\$ @PeterTaylor Thank you for those points: Yes I think I should exclude the case that the factors are not coprime, (gcd of all factors (together) is 1). What do you think would be a good input/output mechanism? I think a function that accepts and returns the strings would be appropriate. Regarding the examples: Up to now I did not consider providing test cases, but of course I need to! I want to point out one tricky part of the task as it is now: A polynomial can be a product of two irreducible polynomials, so that the polynomial itself is not irreducible but also doesn't have linear factors. \$\endgroup\$ – flawr Jul 8 '14 at 6:18
  • \$\begingroup\$ [continuing] Do you think that this is too difficult? I also thought about reducing the task to polynomials which have maximum one irreducible factor. I mean quite a bit of math is required in order to determine the irreducibility. A way simpler task would be the factorization of a polynomial that consists only of linear factors... \$\endgroup\$ – flawr Jul 8 '14 at 6:23
  • \$\begingroup\$ True, you should have a test case for that too. But it's not necessary to restrict the task to polynomials which are a product of linear factors and one irreducible factor, because it's not necessary to test irreducibility. On the assumption that this is a code-golf, I would expect everyone to use the Cauchy bound on the real roots. \$\endgroup\$ – Peter Taylor Jul 8 '14 at 8:13
  • \$\begingroup\$ A function which takes a string and returns a string is fine, although you might want to say "function, named block, or named verb" to cover some of the languages which are used a lot more on this site than in the real world. \$\endgroup\$ – Peter Taylor Jul 8 '14 at 8:18
  • \$\begingroup\$ Well you do not have to use the bounds, since all the roots have to divide the constant term. \$\endgroup\$ – flawr Jul 8 '14 at 11:10
1
\$\begingroup\$

Build a GenericScript Compiler

Your task is to build part of a compiler for the new programming language GenericScript. In this challenge you are only required to check the input source code for syntax errors and not build a running program.

Given the source code for a GenericScript program as input, parse the source code to check that it conforms to the syntax rules for the language. The syntax definition for GenericScript is below. If a part of the source code is found to be invalid, a message must be displayed informing the programmer that there is a mistake.

Since the challenge is for syntax only, you are not required to check for correct usage of variables e.g. use of undeclared variable. Only the syntax rules specified need to be checked.

A bonus will be given if the output message includes the line of code where the problem occurs.

Win Criteria

This is code golf. Shortest code wins. Implementing the line number bonus allows you to multiply you score by 0.8 e.g. only 80% of your code length will be counted as your score.

Syntax

"C" style whitespace rules apply i.e. multiple whitespace characters are treated the same as a single whitespace character & whitespace is only required in between tokens if it would otherwise cause syntax ambiguity.

Program             = Statement
Statement           = Assignment | If | Output | Sequence | While | StringDeclaration | BooleanDeclaration
Assignment          = Identifier "=" (String | Bool); 
StringDeclaration   = "string" Identifier "=" String ";"
BooleanDeclaration  = "bool" Identifier "=" Bool ";"
If                  = "if(" Bool ")" Statement ["else" Statement]
While               = "while(" Bool ")" Statement
Output              = "print(" String ");"
Sequence            = "{" [SequenceContent] "}"
SequenceContent     = Statement [SequenceContent]
Identifier          = {Any sequence of alphanumeric characters with at least 7 characters (all language keywords are shorter than this) }
Bool                = BoolConstant | OperatorAnd | OperatorOr | OperatorNot | StringEquals | BoolEquals | Identifier
BoolConstant        = "true" | "false"
OperatorAnd         = Bool "&&" Bool
OperatorOr          = Bool "||" Bool
OperatorNot         = "!" Bool
StringEquals        = String "==" String
BoolEquals          = Bool "==" Bool
String              = StringConstant | OperatorConcat | Input | Identifier
StringConstant      = "'"StringConstContent"'"
StringConstContent  = "\\" | "\'" | Character [StringConstContent]
Character           = {Any character except for "\" and "'"}
OperatorConcat      = String "&" String
Input               = "read()"

Test Input

Valid Input:

print('What is your name?')
string myInput = read();
print('Hello ' & myInput);

Invalid Syntax:

If(read() == 'DoTask1')
  print('Executing you'r command');
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, that sounds like quite a task. A few issues I can think of: a) you should specify exactly how scoping works. b) your first bonus is a bit hard to nail down - how detailed does the error message have to be? And do the strings for those error messages (or any warnings) count towards the code size? Because then this may just devolve into people using ridiculous shorthand for notifications and claiming they are sufficient. c) Are you 100% sure your grammar is complete, correct and consistent? d) You provide a grammar but no definition of the semantics of the individual constructs. (continued) \$\endgroup\$ – Martin Ender Jun 21 '14 at 17:07
  • \$\begingroup\$ Most of the symbols have an implied meaning, but there doesn't seem to be a specification what any individual literal, operator or function is supposed to do, so any compiler that checks the syntax could claim it compiled the program correctly based on some arbitrary spec. \$\endgroup\$ – Martin Ender Jun 21 '14 at 17:08
  • \$\begingroup\$ Don't get me wrong, I quite like the idea, but it seems to be a bit too much of a mammoth project to work well on PPCG - the main problem being that this is very prone to little mistakes not being caught before the challenge goes on main and people start working on it... which just leads to frustration all around. \$\endgroup\$ – Martin Ender Jun 21 '14 at 17:09
  • \$\begingroup\$ @m.buettner Thanks for your feedback. I have simplified the chalenge and simplified the syntax rules. \$\endgroup\$ – rdans Jun 22 '14 at 12:14
  • \$\begingroup\$ Is it case-sensitive? If yes, then your syntax list contains some case-changes. \$\endgroup\$ – Kyle Kanos Jul 2 '14 at 2:41
1
\$\begingroup\$

Survival of the fittest

As Chris Jester-Young suggested here, i will propose my challenge here. At the moment, this is merely a draft but i want to ask for suggestions to this idea as early as possible.

For discussions, i suggest using the chatroom at chat.stackexchange.com specifically for this challenge.

My draft in its newest state plus all source code is hosted at github where you can make pull requests with suggestions.


The post here consists of the rules my challenge will have. Look at the github to see a lengthy explanation of what i post here. Feedback of all kind is appreciated!


Rules

Board

The challenge is held on a two dimensional board with x and y coordinates. 0|0 is on the left-top side and increases in y downwards and in x to the right. Every field on the board can only hold one object. Objects are all kind of things in the game, from resources to units and even buildings. Board corners are solid, so the board is surrounded by walls. Everything on the board is randomly distributed. The board size is determined by the number of players in the game.

Actions

Every AI acts as one faction of humans. These factions have their explicit name and can be recognized by all other factions. Each round, all factions are given the complete board state and they have to submit some actions. Actions will be executed based on the time stamp of submission. So a faster calculating AI has the benefit of moving first. Animals and NPCs will move after all actions from the AIs are executed. Then there is a new round.

Game limits

The game ends, when there is only one faction left. There can be a time limit, if is turns out to take ages... There will also be a time limit for each round. Taking more time than the limit means, your program will be cut off and the rest of your actions will be omitted. After 5 consecutive rounds hitting the time limit, an AI will be disqualified.

Gameplay

Each faction starts the game with four workers and a stockpile. They have to collect wood, stone and food to survive. Food is used up every round to fill the workers stomach. All three resources will be needed to construct buildings and advance in technology and in numbers. Workers are able to reproduce in housings. but they can also be converted to soldiers. Soldiers can not work nor reproduce, but excel in their fighting ability. With more advanced technology, workers can be converted to better soldiers. Soldiers can not be upgraded.

Strategy

There are numerous buildings available and the more advanced cost a huge amount of resources. Fighters can destroy buildings, while workers can conquer them. Buildings allow for things like reproductions, boosts on resource collection and overall attributes of each unit. Units get more experienced in things, while they are doing them. This experience is handed down to the next generation. Since there need to be two units, to get an offspring, a genetic algorithm will mix their abilities together. This can be better or worse. Your units can have offspring with units from other factions, but both units have to agree on the matter. The offspring randomly chooses between the two factions and stays there.

Control

The AI does not control its units directly. It only gives orders. There is no limit on how many orders an AI can give each turn but every unit can only have one active order at a time. Giving a second order overrides the first one. Units try to execute the orders that are given to them. They are doing this automatically and orders are carried to the next round, if they are not fully completed. While the AI hat full informations over the board, their units have not. Giving an attack order to a place the unit can't see, the unit will try to walk there and attack when in view of the target.

Alliances

There is a global chat that all AIs share and where all AIs can talk to while calculating actions. AIs can specify other AIs that they think are friendly. They can not attack these. If two AIs each think of each other as friendly, they from a bond. A chain of such bonds is called an alliance. Even if you do not consider them friendly, your alliances friends are not attackable for you. So forming an alliance with someone, who friends everyone means, you cannot attack anyone, but they can attack you, if they don't friend back. Each round you can alter your friends to your liking. There is no such thing as an alliance chat, so you have to use encryption to chat in secret. And remember, in the end, only one AI wins the game.

Scoring

Scoring is done in number of rounds survived. Perhaps there will be some more scoring factors included to make the game more interesting.


Please bear in mind, that i will edit this answer a lot the next time to reflect the changes in the challenge.

\$\endgroup\$
  • \$\begingroup\$ This is rather vague at the moment. What do you want feedback on? \$\endgroup\$ – Peter Taylor Jul 12 '14 at 17:10
  • \$\begingroup\$ I wanted to propose the idea of a challenge like this here first. I am at the moment thinking about the rules of the challenge. Any 'Hey, xyz would be cool!' or 'what if abc?' helps me. It will get less vague soon! Until then, every meta-feedback on the challenge is appreciated. Just speak out your mind. \$\endgroup\$ – reggaemuffin Jul 12 '14 at 17:16
  • \$\begingroup\$ @PeterTaylor I have now written an outline of the rules, this challenge will have. Can you look over it and tell me, if something is unclear? \$\endgroup\$ – reggaemuffin Jul 12 '14 at 19:43
  • \$\begingroup\$ I suggest to add titles to each text-section you have. It is quite hard to read right now... \$\endgroup\$ – CommonGuy Jul 14 '14 at 12:04
  • \$\begingroup\$ @Manu I have added some titles that seem to fit well. Do you have any other suggestions? \$\endgroup\$ – reggaemuffin Jul 14 '14 at 13:16
  • \$\begingroup\$ @Kostronor much better :) As Peter Taylor said, everything is rather vague. Try to specify rules, such as the time limit, actions and so on... \$\endgroup\$ – CommonGuy Jul 14 '14 at 13:25
  • \$\begingroup\$ @Manu My intention for this project is to make something a bit more complex, that has many distinct strategies to win. I am writing on the controller at the moment, which helps me specify the rules in a more detailed manner. Until then, can you give me some feedback on the overall gameplay? Do you think, this could be interesting? \$\endgroup\$ – reggaemuffin Jul 14 '14 at 13:35
  • \$\begingroup\$ @Kostronor Sure it is interesting. I hope it doesn't get too complicated ;) \$\endgroup\$ – CommonGuy Jul 14 '14 at 13:39
  • \$\begingroup\$ This sounds really interesting to me. However, especially due to the complexity, be prepared to get only a handful of submissions. So far the popular KotH's were popular because you could whip up a simple bot in a couple of minutes (which wouldn't have any chance of winning, but it's fun posting it anyway to get the ball rolling). If your game is sufficiently complex that even the most basic strategy takes half an hour and some debugging to implement, that will put a lot of people off (who might take this on them if there are already simpler submissions to be beaten). \$\endgroup\$ – Martin Ender Jul 15 '14 at 23:06
  • \$\begingroup\$ Btw, I really like the idea of handling commands in the order they come in! :) \$\endgroup\$ – Martin Ender Jul 15 '14 at 23:06
  • \$\begingroup\$ @m.buettner I thought, to lower the starting requirements, i will write some basic bots myself, where everyone can start. I think, the main focus should be on the strategy and not on the coding, so i will try and get some abstraction done, like the example bots from 'petri dish'. Yeah, the commands in order thing is something, that trades of better action against faster thinking. But it's a pain to implement it ;) \$\endgroup\$ – reggaemuffin Jul 16 '14 at 9:25
1
\$\begingroup\$

Empire wars

This is very close to Risk, but not quite. You command an empire, composed of armies, trying to take over the world.

The world

The world is a grid. For n competitors, the side length of the grid is sqrt(n)*4 (casted to an integer). At the beginning, the world is part of the "neutral" empire. Each neutral army contains 200 soldiers. The neutral army only defends, it never attacks. Your starting army of your empire is randomly selected from the grid. Note that the world wraps around if you go off the edge.

Receiving soldiers

Every turn, you will be given 500 + 50t soldiers to distribute, where t is the number of armies/territories you command. You can give any amount to any army, as long as you don't exceed 500 + 50t in total.

You may then attack or transfer any number of soldiers to another location.

That means that, if you have enough soldiers, you can move soldiers from multiple different territories to multiple new territories.

Attack/Transfer

During your turn, you may move any number of soldiers from any of your armies to any of the squares bordering your army. You can move diagonally. One of two things will happen

  1. You already control the square your army is moving to: Nothing special. The new square gets some more soldiers.

  2. Another empire controls the square: The two armies will fight (see below). If your army wins, the surviving soldiers will inhabit the territory. Otherwise, any surviving soldiers will retreat back.

Battle

The order of battle is randomized every turn, because the empires who go first have a slight advantage or disadvantage (depends on the algorithm). For example, if I occupy a territory on my turn, but I go before another empire, then that empire could potentially attack my new territory.

Suppose a is the number of soldiers attacking and d is the number of soldiers defending. The defenders lose a * 0.6 soldiers and the attackers lose d * 0.7 soldiers. If the defenders have no soldiers remaining, the attacker's surviving soldiers inhabit the territory. For example, suppose the world looks like:

N-200 N-200 N-200 N-200
N-200 N-200 N-200 N-200
N-200 N-200 A-500 N-200
N-200 N-200 N-200 N-200

where N-200 represents a neutral army with 200 soldiers and A-500 represents an army of your empire. Suppose the following happens:

  1. Your empire (A) decides to move 250 people north. First of all, north is not controlled by your empire, so a battle is started. N-200 loses 250 * 0.6 soldiers and A-500 loses 200 * 0.7 soldiers, with a result of N-200 --> 50 and the 250 attacking soldiers will be reduced to 110. Since the territory wasn't conquered, the 110 survivors retreat. The world will now look like:

    N-200 N-200 N-200 N-200
    N-200 N-200 N-50 N-200
    N-200 N-200 A-360 N-200
    N-200 N-200 N-200 N-200
    
  2. You now decide to move 180 people north. The same thing happens: N-50 loses 108 soldiers and A-360 loses 35 soldiers. Since N-50 has been eliminated, the remaining 58 soldiers move into the new territory.

    N-200 N-200 N-200 N-200
    N-200 N-200 A-58 N-200
    N-200 N-200 A-180 N-200
    N-200 N-200 N-200 N-200
    

Note that neutral territories never attack.

Example implementation:

The code should be in Java (thinking of extending it to other languages) and needs to extend the abstract class Empire.

// The code MUST be in the package "empire" and extend the class "Empire" from mainengine
package empire;

import java.io.IOException;
import java.util.List;

import mainengine.*;

public class TestEmpire1 extends Empire {
    // Occurs at the beginning of the turn
    // You get 500 + 50t soldiers to deploy
    @Override
    public void deploy(ArmyDeployer toDeploy) {
        // Get all of my armies
        List<Army> armies = getArmies();
        // Distribute my new armies to each army evenly
        int perArmy = toDeploy.armiesLeft() / armies.size();
        for (Army a : armies) {
            a.addPower(toDeploy, perArmy);
        }
    }

    // You can move your armies as well
    @Override
    public void move() throws IOException {
        // Get the world
        World world = World.world;
        // Get the map of the world
        // Note that you can only see the areas adjacent to your armies
        // All other locations appear as "null"
        Army[][] map = getMap();
        for (Army a : getArmies()) {
            // Find the least guarded territory
            Move bestMove = null;
            int leastDefended = Integer.MAX_VALUE;
            for (Move move : Move.values()) {
                int newX = world.wrapPosition(move.getXOffset() + a.getPoint().x),
                    newY = world.wrapPosition(move.getYOffset() + a.getPoint().y);
                if (map[newY][newX] != null && map[newY][newX].getStrength() <= leastDefended) {
                    leastDefended = map[newY][newX].getStrength();
                    bestMove = move;
                }
            }
            // Attack with half of our strength
            a.move(bestMove, a.getStrength() / 2);
        }
    }

}

See github for the code that will be executing it: https://github.com/prakol16/EmpireWars/tree/master/EmpireWars/src

The "number of points" that an empire receives is how many territories it controls after one run (about 50, subject to change, or so turns). The program will be run 10 times and the empire with the most total points wins.

In addition, the program creates an html file record.html which contains a record of every turn.

\$\endgroup\$
  • \$\begingroup\$ Sounds interesting! :) A few comments: 1. I don't think this is very close to Risk. I'd say "inspired by Risk" is as close as it gets, because I suspect the battle system to play out vastly differently (for instance, attackers are always at a disadvantage here). 2. Up until your example it's not clear that neutral territories are occupied by some army, and that this neutral empire starts with 200 soldiers on each cell. 3. Since this caused some confusion recently, I'd remove "the world is round" (and only mention that it wraps around), because it implies that the world is spherical... [ctd.] \$\endgroup\$ – Martin Ender Jul 15 '14 at 9:36
  • \$\begingroup\$ in which case north/south wouldn't wrap around. A map which wraps on both edges is in fact in the shape of a torus, but mentioning that would probably confuse some other people, so I'd say only state that both edges wrap around and nothing else. 4. How many are "many rounds" (after which the game ends)? 5. You might want to think about providing a wrapper implementation of Empire which calls a separate process, in order to allow submissions in other languages. Like Rusher did here. 6. Can I attack and transfer... [ctd.] \$\endgroup\$ – Martin Ender Jul 15 '14 at 9:40
  • \$\begingroup\$ units from multiple territories into multiple territories within a single round? Or do I have to stick to one transfer or one (repeated) attack? 7. I suppose the order of players will be randomised? I also expect a fair share of submissions to be probabilistic. In that case deciding the overall winner based on a single run might not be fair (unless the winner is always the same submission anyway). Are you prepared to run multiple simulations if that happens (such that the winner is submission that wins the largest number of individual simulations)? \$\endgroup\$ – Martin Ender Jul 15 '14 at 9:43
  • \$\begingroup\$ @m.buettner Ok, updated some stuff. For #4, 7: I'm not sure how many yet, but it should be enough that luck doesn't affect the empire that much. For #6: Yes, you can send different commands to multiple armies in different locations. Just note that if you occupy a new territory, it won't be available for you to command until the next turn. #7. Yes, the order is randomized every turn, because if I occupy a territory, even though I can't command it immediately, another empire could still attack me immediateley. \$\endgroup\$ – soktinpk Jul 15 '14 at 14:47
  • \$\begingroup\$ Alright, thanks for clarifying. I don't like the idea of sending your orders before everyone makes their turn. You'd have no idea what would happen to the territories you're attacking before you're actually invading there. 8. How many soldiers do I have to leave behind when attacking/transferring? \$\endgroup\$ – Martin Ender Jul 15 '14 at 14:55
  • \$\begingroup\$ @m.buettner You could potentially leave none when attacking/transferring. That would leave the territory completely undefended though. As for sending your orders before everyone makes their turn: if it isn't done this way, then the people who go first have a huge disadvantage because they don't know anything about who's attacking the territory, while the ones who go last have lots of information. Your orders should be based on what's currently there (what happened in the previous turn) \$\endgroup\$ – soktinpk Jul 15 '14 at 15:21
  • \$\begingroup\$ If you buffer the orders, those going at the end will have a huge disadvantage because they have no idea what the map will look like when their order is actually carried out, whether there's no uncertainty at all for those going first. I think this difference is much more unfair than the first player having to make a decision before everyone else. 9. Do you get your soldiers when it's your turn or does everyone get their soldiers at the same time once everyone's moves have been completed? \$\endgroup\$ – Martin Ender Jul 15 '14 at 15:32
  • \$\begingroup\$ @m.buettner I see your point. I don't think I'll buffer the orders then (it makes more sense not to now that I think about it). 9. Everyone gets soldiers at the same time. \$\endgroup\$ – soktinpk Jul 15 '14 at 15:38
  • \$\begingroup\$ You could look at the board game Diplomacy for some ideas about how to handle simultaneous resolution of everyone's orders. (I confess that I don't know offhand whether it's a good system, but I do know that it's a system). \$\endgroup\$ – Peter Taylor Jul 15 '14 at 16:42
1
\$\begingroup\$

XKCD: (Battle of the) Hats

http://imgs.xkcd.com/comics/hats.png

Enough background, get into the game

A challenge.

You all started at a point. At the count on 3, you decides to wear yourself 1 black hat, 2 black hats or 1 white hat.

Here's what happened: (If you find this description confusing, you can look at the table below, credit to Peter Taylor)


If you use 1 black hat ->

-> If your opponent also uses 1 black hat or white hat, your opponent moves backward 1 step.

-> If your opponent uses 2 black hats, you have 50% chance making your opponent moves 2 steps backward. Else your opponent does nothing.


If you use 2 black hats ->

-> If your opponent doesn't use white hat, your move is considered successful 2 black hats attempt. Your opponent moves backward x+3 steps, where x is # of your previous successful 2 black hats attempt.

-> Else: Your attack gives no effect.


If you use white hat ->

-> If your opponent use 2 black hat, you're considered making successful white hat attempt. Your opponent moves backward y+3 steps, where y is # of your previous successful white hat attempt.

-> Else: You're considered making a failed white hat attempt. You move backward z+3 steps, where z is # of your previous failed white hat attempt.


The game ends when somebody moves 20 step backward or 10 rounds played.

If one person moves 20 or more steps backward while one doesn't, then the one who not is declared the winner.

If both moves 20 or more steps backward in the same round or no one moves 20 or more steps backward in 10 rounds, no one win.

Your bot will play 5 tournaments. In each tournament, you face each enemy once. The player who score most win in those 5 tournaments accumulated, is declared the champion

Communication Protocol

Your bot will get this from STDIN:

id round step0 step1 move0 move 1

Where id is your player id, can be 0 or 1; round means current round (match starts at Round 1); step0 and step1 means how many step has player 0 and player 1 has taken; move0 and move1 is the move taken by player 0 and player 1.

In first round, move 0 and move 1 will be empty. In next round, it will the move as this

12w21

This means one player use 1 black hat; 2 black hats; white hat; 2 black hats; 1 black hat, respectively.

Your bot gives me output from your STDOUT as 1 if your bot want to wear 1 black hat, 2 if your bot want to wear 2 black hats, w if your bot want to wear white hat.

PS: Do aware that I use small-case "w"


Table:

                +--------------------+--------------------+---------------------+
                |                    |     P0 action      |                     |
                |         1          |         2          |          w          |
+---------------+--------------------+--------------------+---------------------+
|             1 | P0 back 1          | P0 back 0 or 2     | P0 back z0+4; z0++  |
|               | P1 back 1          | P1 back x0+3; x0++ | .                   |
+---------------+--------------------+--------------------+---------------------+
| P1 action   2 | P0 back x1+3; x1++ | P0 back x1+3; x1++ | .                   |
|               | P1 back 0 or 2     | P1 back x0+3; x0++ | P1 back y0+3; y0++  |
+---------------+--------------------+--------------------+---------------------+
|             w | .                  | P0 back y1+3; y1++ | P0 back z0+3; z0++  |
|               | P1 back z1+4; z1++ | .                  | P1 back z1+3; z1++  |
+---------------+--------------------+--------------------+---------------------+
\$\endgroup\$
  • \$\begingroup\$ 1. The scoring table would almost certainly be easier to read in a table. 2. Could you be more precise in the definition of x, y, z? Whose previous moves are counted, and what counts as "successful"? 3. In the "You move z+3 steps", is that forwards or backwards? 4. Is it intended that the bots should not know what x, y, z are? 5. It makes more sense for the controller (of which there is one) to handle the naming issue and let each bot (maybe a dozen) handle the simple case of always being player 0. \$\endgroup\$ – Peter Taylor Aug 22 '14 at 11:28
  • \$\begingroup\$ You can figure x y z from history move. For the scoring table, I cant figure out how to make this without using image (trying to make this as html as possible), I shall rewrite the 2 black hats and white hats. \$\endgroup\$ – Realdeo Aug 22 '14 at 11:36
  • \$\begingroup\$ I agree that a table that is not an image would be better, but until you find a way to make that work, please could you include an image of a table? \$\endgroup\$ – trichoplax Aug 22 '14 at 11:47
  • \$\begingroup\$ The table won't fit or render correctly in a comment, so I've added it to the answer. \$\endgroup\$ – Peter Taylor Aug 22 '14 at 11:58
  • \$\begingroup\$ Thank you. I have credited you. \$\endgroup\$ – Realdeo Aug 22 '14 at 12:04
1
\$\begingroup\$

Making a dichotomous key

A dichotomous key, also known as a single-access key is often used to identify plants/animals. Your task is, given a set of data, write the shortest program that outputs the shortest (in steps) possible dichotomous key. If there are multiple solutions, the program may print either one.

Input

Input will be received by stdin, or in cases where that doesn't exist (e.g. Client-side javascript) you can take input from prompt or something similar.

The input will be a list of items followed by characteristics: The format of the definition of an item will be

item[delimiter1]characteristic1[delimiter2]characteristic2[delimiter2]characteristic3

Your program may choose the delimiters. In this example, I will use : as delimiter one, and , as delimeter 2. Between each item definition is delimiter3, which will be \n in this example (but you can make it anything that isn't delimiter1 or delimiter2). Note that none of the delimeters can be [a-zA-Z] letters.

Characteristics and items are composed of a series of [a-zA-Z] characters.

Example input:

quadrilateral:fourSides
trapezoid:fourSides,onePairParallel
parallelogram:fourSides,twoPairsParallel,oppositeSidesEqual
rectangle:fourSides,twoPairsParallel,fourRightAngles,oppositeSidesEqual
rhombus:fourSides,twoPairsParallel,oppositeSidesEqual,allSidesEqual
square:fourSides,twoPairsParallel,oppositeSidesEqual,allSidesEqual,fourRightAngles

Output

Output should be written to stdout, or alert or something similar where it doesn't exist.

You must output a characteristic followed by delimiter one, followed by two integers separated by delimiter two. The first is the step to go to if the item contains the characteristic, and the second is the step to go to if the item doesn't contain the characteristic. Note that the 1st step is considered 0. Alternatively, instead of an integer, you could have an item.

Example output:

twoPairsParallel:2,1
onePairParallel:trapezoid,quadrilateral
allSidesEqual:3,4
fourRightAngles:square,rhombus
fourRightAngles:rectangle,parallelogram

This is code-golf so shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ The example output looks wrong to me. Shouldn't the first line be twoPairsParallel:2,1? Also, since the transformation doesn't inherently use any biology at all and since you use shapes, it would be clearer to talk in terms of "classes" or "taxons" rather than "organisms". It's also good to be explicit about I/O assumptions; since you talk about a program and string delimiters between items in a list, I would guess that you want a full program which takes input from stdin and writes output to stdout. State that. \$\endgroup\$ – Peter Taylor Aug 22 '14 at 8:36
1
\$\begingroup\$

This is nearly done now, just need someone to double check that everything makes sense

Generate Lightning Forks in a 3D Grid

Objective:

Overview:
Write a program, that given the two inputs number of rays and ray length, will produce a procedurally random array of connected points, containing the ray number, number in sequence and coordinates of each point.

Details:
The lightning is in the form of rays, which are determined by points stored as coordinates in a grid.

The initial point (0,0,0), is the cloud, where the lightning is first generated. The first ray starts here and travels out in a random direction, and will continue moving in random directions (each point has an equal chance of any direction, not influenced by the previous point), and will terminate once it reaches the ray length limit or cannot go any further (if it fails enough new direction retries when intersecting with another point). This will leave a single path between the origin and the end point.

However, lighting doesn't stay as one single ray and will fork, so while all other rays should be generated in a similar way, their origin should be randomly chosen from any of the already generated points, and the sequence then continues from this point.


The Ray Number is simply which ray iteration the code is on. Each ray is it's own individual path. The origin point of the ray will have the same coordinates as the point it branches off from.

The Number In Sequence is how many points away from the cloud (or how far into the generation) it is. If lightning forks at point 50, both separate paths will start at 51. While this is not currently used for anything aside from checking the code is working correctly, it would allow for future improvements such as animation (see gif at bottom for an example).

Coordinates are the 3D points the ray passes through. They should be stored as integers.


Simple 2D Diagram:
Here is an example output during generation after 24 points have been calculated.
The numbers written in black are the numbers in sequence, and as you can see when the 2nd ray (blue) branches out, it continues from 10. The red line is an example of when it would try intersect with existing points and get stuck. This shows the cloud as it's own ray, you are free however to do this differently. diagram

Rules:

  • Can be written in any code (without extra plugins), although I can't guarantee anything but PHP and Python will be tested, unless someone else with access to a lot more languages helps out.
  • Randomness must be seed based, so if you were to define a seed (not needed), it would produce the same result.
  • A point can move in any one of the 3 dimensions - meaning it can go up, down, left, right, forwards, or backwards (x,y,z,-x,-y,-z) from the previous point, but not diagonally.
  • No two points can have the same coordinates.
  • The one exception of this rule is that each ray must start with the same coordinate of where it branches out (for the purpose of connecting everything together).
  • If an intersection is detected, at least 3 retries must be done to find new direction, then it may be terminated. The retries must be for each point, so having 1 retry on 3 different points shouldn't terminate the ray.
  • No multithreading allowed.
  • The code should output the final number of points generated and time taken.
  • The program should be timed to when the array of points is complete. Anything after this (such as for the bonus points) is fine and won't impact on the execution time.

Scoring:

  • Generate 100 rays with a maximum length of 200. If your code is super efficient and you want to show off, you're welcome to post the times for more complex results.
  • Most efficient code wins, based on the execution time. Someone will test multiple submissions and take an average from at least 4 generations to make it more fair.

Important: So I can easily check your code works as it should, I wrote something that will display the rays in a 3D program.
You'll need to generate 30 rays with a length of 15, in 2D (easy to switch - where it randomly chooses from from 6 directions, change this to 4), and copy it to pastebin. Format it like I have done here, and keep it limited to square brackets, commas, and integers: http://pastebin.com/8XHtv4is

Bonus Points:

  • Given any two random points, there is one and only path between them both. If you can code something that would be able to calculate a path between these two random points and store it in a new array with the same structure, you get 15% off the execution time.

  • Instead of limited to 3 dimensions, code it for n dimensions, as more than 3 dimensions should work, despite being a little hard to visualise. If you manage you can knock 10% from the execution time.

  • As not everyone will be able to do it, this is only worth 5%, but you get it, if you code a way to visually draw the rays (2D is allowed, any method is allowed, but it must be able to run at the end of the code, as opposed to copying the list into a graphing program).

Tips:

  • Start working with a 2D grid for easier debugging.
  • Use small ray length and ray amount values until properly optimised.
  • While intersections are fairly easy to see, diagonals are not, running the code with a single short ray to print the output can be useful.

Example code:

Generation Time for 100x200: 75-85 seconds

length=15
forks=30
import time
import random as rd
startTime=time.time()
def getDirection(num):
    if(num==1):
        direction=[1,0,0]
    if(num==2):
        direction=[-1,0,0]
    if(num==3):
        direction=[0,1,0]
    if(num==4):
        direction=[0,-1,0]
    if(num==5):
        direction=[0,0,1]
    if(num==6):
        direction=[0,0,-1]
    return direction
listOfPoints = [[0,[0,0,0],0]]
for i in range(forks):
    randomPoint = listOfPoints[rd.randint(0,len(listOfPoints)-1)]
    start = randomPoint[0]
    newLocation = randomPoint[1]
    listOfPoints.append([randomPoint[0],randomPoint[1],i+1])
    j=0
    j2=0
    while j in range(length):
        j+=1
        oldLocation = newLocation
        k = 0
        while True:
            invalid = 0
            newDirection = getDirection(rd.randint(1,6))
            newLocation = [oldLocation[0]+newDirection[0],oldLocation[1]+newDirection[1],oldLocation[2]+newDirection[2]]
            for n in range(len(listOfPoints)):
                location = listOfPoints[n][1]
                if location==newLocation:
                    invalid = 1
                    newLocation = oldLocation
            if invalid==0 or k>4:
                break
            k+=1
        if invalid == 0:
            listOfPoints.append([j2+start+1,newLocation,i+1])
            j2+=1

print "Time: "+str(round(time.time()-startTime,2))+" seconds"
print "Generated/Maximum points: "+str(len(listOfPoints))+"/"+str(length*forks)+"("+str(round(len(listOfPoints)/float(length*forks),3))+"%)"

Visualised Output:

(From a more advanced version I did before, I was aiming to make a flower)
diagram

\$\endgroup\$
  • \$\begingroup\$ You seem to be using the word "fork" to mean two different things: a single line of points, and a bifurcation where one line becomes two. Perhaps you could use "ray" for the first, since it's conceptualised as a lightning simulator. You also seem to use "point" to mean "point in an integer lattice", but I don't think you actually state anywhere that you're working solely in integers. \$\endgroup\$ – Peter Taylor Aug 20 '14 at 20:26
  • \$\begingroup\$ Is the cloud at the origin (0,0,0)? Does the first ray travel in a random direction, or always in the same direction? When the first bifurcation is created by picking a random point on the first ray, does the second ray travel in a random direction or always in the same direction? If in a random direction, what happens if the direction selected is parallel with the first ray? \$\endgroup\$ – Peter Taylor Aug 20 '14 at 20:26
  • \$\begingroup\$ The explanation of bifurcation says that "However, lightning doesn't stay as one straight line, so for the second fork..." This strongly implies that each ray is a straight line. But the 2D diagram shows rays changing direction a lot. What is the correct generation process for a single ray? For the "cannot go any further" termination process to kick in, does it have to be unable to go in any direction at all, or just to pick a random direction which is blocked? (This is partially explained further down in the rules, but it would be convenient to group the explanation in one place). \$\endgroup\$ – Peter Taylor Aug 20 '14 at 20:28
  • \$\begingroup\$ What is the point of the unique ID? Each tuple would already appear to have at least one primary key: the (fork number, number in sequence) pair. The later rules seem to make it clear that the coordinates are also a primary key. Separately, what are the parameters of the simple 2D diagram? In particular, what is the fork length? The red line seems to imply a lower bound of 13, but the blue line isn't that long. \$\endgroup\$ – Peter Taylor Aug 20 '14 at 20:28
  • \$\begingroup\$ You can pretty much guarantee that someone will be able to test most obscure languages posted here. See also this meta thread. Up, down, left, right, forwards, and backwards are 6 directions, not 6 dimensions. It sounds like you actually want 3 dimensions. There's no point posting obfuscated example code. In general, it's better to post a reference implementation as an answer to avoid clutter. The 2D visualised output is unhelpful. I would remove it to avoid confusing people. The hand-drawn 2D image is a lot more useful. \$\endgroup\$ – Peter Taylor Aug 20 '14 at 20:29
  • \$\begingroup\$ The bottleneck for many implementations could well be the I/O, so you should explain how you will take that into account when measuring performance. On the bonuses: Calculating the path between two items in a tree should be pretty simple: you track back from both until you find a common ancestor. But even though it's simple, you don't say how much of a bonus it gives. The other bonus confuses matters slightly when it says that it "should technically work for infinite dimensions": actually, it can't, because there's no fair probability distribution over an infinite set. \$\endgroup\$ – Peter Taylor Aug 20 '14 at 20:30
  • \$\begingroup\$ Thanks for the comments, I'll reword the question and set it to generating lightning forks, gives it a better title. As to the potential infinite dimensions, how would you reword it? I could manually code in 100 dimensions if I wanted to spend 20 minutes doing it, I'm just suggesting someone codes the option where it'll do it automatically. \$\endgroup\$ – Peter Aug 21 '14 at 0:15
  • \$\begingroup\$ Oh also, as to the bottleneck you mentioned, that's the main efficiency problem, I'm curious if anyone can find a method that doesn't involve reading the entire list every time a new point is added \$\endgroup\$ – Peter Aug 21 '14 at 0:42
  • \$\begingroup\$ Hey, just updated it again, do things make a lot more sense now? \$\endgroup\$ – Peter Aug 22 '14 at 20:53
1
\$\begingroup\$

Confused Automatons

[work in progress]

This is a 1v1 (or not? could be more) king-of-the-hill, where you and your opponent both issue commands to the same, perpetually confused, gladiators and try to survive.

Toroidal arena with N gladiators. They understand the following simple commands:

  • Move one of 8 directions or
  • Hold

plus one of:

  • Shoot target. Range of 5. Can’t shoot the following turn.
  • Dodge (no target required)
  • Nothing

On each turn you may issue one command ([M/H]+[S/D/N]) to each gladiator. All gladiators will execute the commands from both players each turn. Movement happens first. If a gladiator is given two shoot commands, they will shoot twice that turn; two dodge commands and they will dodge twice. One dodge will avoid one shot. A gladiator can't shoot himself. Movement in opposite directions will cancel; movement in the same direction means moving a distance of two. If there is both an [H] command and an [M] command for the same gladiator, the [H] will be ignored.

One of the gladiators is your commander. You lose when your commander dies. Your commander ignores commands from your opponent. You don’t know which gladiator is your opponent’s commander.

Input

TBD

Output

TBD

Scoring

TBD

\$\endgroup\$
  • \$\begingroup\$ I am just as confused as the automoton. Won't you easily be able to figure out which gladiator is the commander by seeing who ingored the command? \$\endgroup\$ – Rohan Jhunjhunwala Jul 16 '16 at 1:18
1
\$\begingroup\$

Unicode Case Mapping

Challenge:

Given a string as input, print it in both lowercase and uppercase.

The string will be valid UTF-8, and your output should be as well. Characters without lowercase or uppercase mappings should be printed unmodified. Invalid, un-assigned, and private-use characters need not be handled.

Uppercasing and lowercasing should be doing according to Unicode 7.0 "simple" case mapping rules.

Rules:

This is code-golf, shortest program wins. Your program shouldn't use any external data files or access anything from the internet; all of the information it needs should be contained within the code itself.

You may not use your language's built-in case-mapping functions, built-in copies of the Unicode Character Databse, or libraries such as ICU. For example, in Perl the lc and uc functions as well as Unicode::UCD are prohibited.

Since this challenge is about Unicode I will throw in a small scoring twist: if your program is valid Unicode text (in whatever encoding your language prefers, probably UTF-8) you may score it at a rate of one point per character (regardless of how many bytes those characters take up). If it contains binary data then it must be scored at one point per byte. I will clarify what constitutes "binary data" if I have to.

Bonus:

Support "full" Unicode case mapping. The difference between "full" and "simple" mapping is that in "simple" mapping every codepoint maps to a single codepoint, while in full mapping a codepoint may map to multiple codepoints. For example, the uppercase of the character "ff" (U+FB00) is "FF" (U+0046 U+0046). Assume that all "conditions" are false (that is, any rule with a non-empty condition_list should be ignored).

Question: offer a point bonus for this? Recognize a separate winner among people that manage it? Drop it entirely?

Resources:

\$\endgroup\$
  • \$\begingroup\$ Created at the suggestion of @guifa after this challenge. \$\endgroup\$ – hobbs Sep 1 '14 at 6:05
  • \$\begingroup\$ Interesting and to the best of my memory not a dupe. It's going to need a good set of test cases, and they may need to be provided in base64 or hexdump format. \$\endgroup\$ – Peter Taylor Sep 1 '14 at 17:25
  • \$\begingroup\$ @PeterTaylor I have no problem supplying those :) \$\endgroup\$ – hobbs Sep 1 '14 at 17:40
  • \$\begingroup\$ Do empty characters like '󠀠' count towards the score? \$\endgroup\$ – Vi. Sep 6 '14 at 12:06
1
\$\begingroup\$

King of the server - virus wars

  • There is a virtual machine with Linux running various services (SSH server, Apache (with SSL), FTP server, rsync server, etc);
  • There is tool which checks that the server is running (periodically accessing all its services - trying to view the page from Apache, download a file from FTP server, etc.) and analysing responses for special ID codes;
  • There are submissions that are started on the server as root and should "inject" some ID code (individual per solution) in as much as possible places while inhibiting competitors;
  • Each solution should try to attain the following goals:
    • Make the server and it's services mention the ID code in maximum number of places with maximum reliability;
    • Avoid stopping the server or breaking any of the services, avoid breaking reboots;
    • Inhibiting competiting solutions (if any) while allowing them to post their ID code at least once;

The virtual machine gets booted, the solutions gets started there, then the script accesses the server from virtual network to check SSH/FTP/HTTP/... still running. The script also looks at the reply and counts any ID codes that appears in the replies. It happens multiple times. The serve gets rebooted N times.

Not all solutions gets planted on the server each time, just some random subset.

A solutions scheduled for the given round receive negative penalty points if:

  1. The server crashed (stopped replying on requests from the virtual network);
  2. Some service on the server crashed (i.e. SSH still works, but HTTP is down);
  3. A competing solution have failed to provide it's ID code even once;

If your solution crashes something or fails to provice the code even once even if run alone (without competitors) - it gets disqualified.

The solutions may use variety of methods to complete the goals:

  1. Just changing configuration in /etc;
  2. Patching system libraries to inject the ID code and/or supress other solutions;
  3. Carrying "clean" copy of libraries to avoid point "2.";
  4. Loading kernel modules;
  5. Extracting competing ID code and manually providing it exactly once (to avoid the "spawn camping" early-kill penalty);
  6. Loading security modules to make root less omnipotent;
  7. Overriding a boot loader, making the server boot nonstandardly...

The virtual machine image will be available from the beginning.

Questions:

  1. Is the idea worth thinking and fits PPCG enough?
  2. Shall all solutions be public from the beginning, or there can be hidden solutions (to prevent easy directed attacks)?
  3. Shall binary-only submissions be allowed?
\$\endgroup\$
  • 4
    \$\begingroup\$ I'm not especially comfortable with this as a concept: it risks crossing the line into writing actual malware. But if you do go ahead with it, it has some other problems which need fixing. Most pressingly, unless the subsets run are fair, it penalises people for ending up in the same run as a bad bot. And that's without taking into account "If your solution crashes something... it gets disqualified". How are you going to attribute the blame when a combination of changes from different bots breaks things? As for binary-only submissions: you'd be foolhardy to run them. \$\endgroup\$ – Peter Taylor Sep 1 '14 at 14:12
  • \$\begingroup\$ As for binary-only submissions: you'd be foolhardy to run them. -> What's the problem? They are expected to be run in a fortified secured environment. Binary-only (or source + binary modified by hand) can be useful to dodge other bots. \$\endgroup\$ – Vi. Sep 1 '14 at 14:39
  • \$\begingroup\$ How are you going to attribute the blame when a combination of changes from different bots breaks things -> The offending bot will get the most penalty (as it probably breaks something every time), and others only sporadically. Subset choice is random. \$\endgroup\$ – Vi. Sep 1 '14 at 14:40
  • \$\begingroup\$ crossing the line into writing actual malware -> 1. It is inspired by how malware works; 2. Finding vulnerabilities is not a priority, as all solutions start as root from the beginning; 3. I haven't seen any anti-malware clauses in FAQ; 4. Bots do "distribute" only by mentioning some hash, not the actual code, client programs (FTP client, browser, etc) are out of scope. \$\endgroup\$ – Vi. Sep 1 '14 at 14:45
  • \$\begingroup\$ Your points 1, 2 and 4 are relevant, but for point 3 I would point out that the FAQs and guidelines of PPCG and SE in general are not the only factors people base their votes on. Even if a question doesn't technically break any rules, it can be downvoted for being unethical, according to the various ethical positions of the voters. Hopefully enough people will share their ethical views here in the sandbox that you can stay the right side of their various lines. \$\endgroup\$ – trichoplax Sep 1 '14 at 16:30
  • \$\begingroup\$ You also need to bear in mind that just because you take steps to make sure a question doesn't result in usable malware doesn't stop the question giving the impression of being about creating malware. Just that potential impression is enough to make some people wary of allowing the question on the site - understandably as it may affect the perception of the site as a whole. Your question has the potential for a very interesting contest but you will have more work to do with this question than your average question due to having to tread carefully. \$\endgroup\$ – trichoplax Sep 1 '14 at 16:37
  • \$\begingroup\$ If you're asking for code which looks like malware, are you 100% certain that you (and everyone else who might want to test it) can tell it apart from real malware? If it's non-obfuscated source you can probably be moderately confident, but if you're allowing binary submissions then I stand by the word foolhardy. As to "the offending bot will get the most penalty", you haven't understood that question. I could rephrase it as "How do you decide which one is the offending bot?" \$\endgroup\$ – Peter Taylor Sep 1 '14 at 17:21
  • \$\begingroup\$ @PeterTaylor, The system should not peep into what actually happens on the server and can only observe crashed vs not crashed. Therefore the only viable option for penalties is to penalize everything, but let the statistics route the most of penalty points to the actual offender. Crashing services is not absolutely prohibited, it just attracts penalty points. But you can't use this tool against somebody else bot, unless it's many on one. The penalty points vs crash probability can be non-linear. \$\endgroup\$ – Vi. Sep 1 '14 at 17:29
  • \$\begingroup\$ @PeterTaylor is right about the binary submissions. Reasonably readable code, though, would make this fun. </2cents> \$\endgroup\$ – Soham Chowdhury Sep 16 '14 at 10:17
1
\$\begingroup\$

Dots and Boxes

The goal is writing a function in [language], that accepts the grid and outputs what dots it wants to connect next. This is a King of the Hill challenge.

How the game works

The (square) field has 6x6 dots. The two players are conenct one after another each time two neighbour dots (vertically or horizontally). If one player closed a square (1x1) in his last step, this square counts as his. The game is finished as soon there are no more dots to connect.

Scoring

Each program will be playing against each other program.

The score is the total number of conquered number of boxes.

Open Questions

  • How can we encode the grid in an easy way as 2D(?) array?
  • How should the function endcode which dots to connect?
  • What language / environment would you suggest for doing so? (It would be easiest if there was only one language. I'd say Python or JavaScript.)
  • Is it better to count the total of the captured squares or only the number of won matches?
\$\endgroup\$
  • \$\begingroup\$ relevant \$\endgroup\$ – Martin Ender Sep 9 '14 at 12:42
  • 1
    \$\begingroup\$ What do you mean by "quadratic"? I think this is a great idea however if you write some nice controller code. The easiest thing is to get the answers to read and write standard input/output I think that way answers can be in any language people want. Your code should verify they make a valid move however and just call the answer code with the new setup. \$\endgroup\$ – user9206 Sep 9 '14 at 12:51
  • \$\begingroup\$ I mean 'square' sorry=) Since I am not THAT good at programming I thougth it would be best doing it in just one (popular and easy to use) language, so I could just copy/paste the code. The requirements for the controller code are: validation of moves, keeping track of the scores (and running all the games) something missing? What do you think about the other Question Another idea I just had was letting ALL the bots play together on one huge arena. \$\endgroup\$ – flawr Sep 9 '14 at 13:51
  • \$\begingroup\$ Here's a suggestion: Squares (or Dots and Boxes as you call it) in four dimensional space. The winner is the person with the most whole tesseracts. \$\endgroup\$ – Beta Decay Sep 10 '14 at 9:45
  • 1
    \$\begingroup\$ Ew. I do not think that I can wrap my head around that=) (I am not even sure whether the game would really work this way) but thanks for the input! Do you have an idea how to encode it in a 2d array? \$\endgroup\$ – flawr Sep 10 '14 at 9:49
  • \$\begingroup\$ This question needs a volunteer to rewrite it I think. It's a great idea but needs some effort from someone generous with their time. \$\endgroup\$ – user9206 Sep 10 '14 at 10:37
  • \$\begingroup\$ What would you change / why would you rewrite it? \$\endgroup\$ – flawr Sep 10 '14 at 11:25
  • \$\begingroup\$ It needs a controller that calls people's code. Their code should take either a move or position as input and return a move. The controller should check this is valid and pass it to the other competitor. This allows people to write their answers in any language they like, \$\endgroup\$ – user9206 Sep 10 '14 at 11:58
  • \$\begingroup\$ Of course but thats on the one hand what we've already discussed. And it makes no sence programming it as long as it is still unsure wheter it will make it out of the sandbox at all. \$\endgroup\$ – flawr Sep 10 '14 at 12:17
  • \$\begingroup\$ I think it won't make it out without a controller. Maybe someone will be kind enough to write one for you. \$\endgroup\$ – user9206 Sep 10 '14 at 12:21
  • \$\begingroup\$ You could have a 2d array of x by y with each element representing the lines between each dot. You could then have populate the array with N as unowned and then have A if the line has been drawn by player A and B if a line has been drawn by player B. Then, you have another x by y 2d array with ownership of each box. \$\endgroup\$ – Beta Decay Sep 10 '14 at 14:00
  • \$\begingroup\$ You could store the grid as a 2D array of the top-left corners. Each point has two lines that go right and down. For the bottom and right sides of the map, there is only one line (unless you want to make a toroidal map) \$\endgroup\$ – Justin Sep 11 '14 at 23:19
  • \$\begingroup\$ @Quincunx thanks, thats a good idea! \$\endgroup\$ – flawr Sep 12 '14 at 9:08
  • \$\begingroup\$ @flawr That's what I did to build my own dots and boxes controller for a KotH that I'm no longer going to host (I don't have time anymore) \$\endgroup\$ – Justin Sep 12 '14 at 13:37
1
\$\begingroup\$

Chad

Chad is a variant of chess. It is played on an uncheckered board measuring twelve by twelve squares. Squares are denoted using standard chess notation, so a12 is the top left corner and l1 is the bottom right corner. The opening position of Chad looks like this:

Opening Position of Chad
Above: Chad gameboard and opening position.

The 3x3 area that the kings start in is called the castle. The twelve shaded squares around each castle is called the wall. Here are how the pieces interact with each other and the wall:

  • The King can move and capture like a King but also as a Knight. However, he is confined to his 3x3 castle.
  • The Rook moves like a Rook in chess, unimpeded by walls or castles. If the Rook ends on a square inside the enemy castle, it is automatically promoted into a Queen.
  • A Queens move like a Queen in chess. She is also unimpeded by walls or castles.
  • The mutual right of capture between two pieces (except for the King) exists if, and only if, one piece is on the enemy's wall, and the other piece is in their own castle. Otherwise, pieces simply block each other.
  • The King may capture pieces inside his castle, provided he can attack the piece (remember that the King can move both as a King and as a Knight).
  • Check occurs if the King is in the path of a Rook or Queen, regardless of whether the Rook or Queen is on the wall or not. Walls do not block checks.
  • As in regular chess, white moves first, a capturing piece replaces the piece captured, and checkmate wins the game.
  • A draw occurs if:
    • x moves have passed without any piece being captured.
    • There is three or less pieces on the board.
    • It is a stalemate.

This is a king-of-the-hill Chad competition. To enter write a program that decides what moves to make, using the IO format below. This program will be pitted against other entrants to find out which program is the strongest.

Inputs and Outputs

Your program will be ran from the command line for each move, and input will be given as a command line argument. Here is the input format:

[colour] [board] [history] [moves]
  • [color] is 0 if you are playing White, and 1 if you are playing Black.
  • [board] is an ASCII representation of the board with newlines stripped. K is a King, R is a Rook. Lowercase letters indicate black, uppercase means white. A dot . is a blank space. The starting position would look like this:

    ...............................rrr.........rkr.........rrr................RRR.........RKR.........RRR...............................  
    
  • [history] is a comma separated list of the moves you and your oppoment have done. It is in a modified long algebraic notation, consisting of the starting and ending squares separated by a hyphen, without a letter identifer for the piece. If it is a capture, the hyphen is replaced with an x. There is no !? or other such ornaments. This is blank if you are White and making the first move - be prepared for this!

  • [moves] is a comma separated list of the valid moves you can make in your current situation. It is also in the modified long algebraic notation.

Note that you don't have to use all of the information given in the input if you do not want to. The information is supplied to simplify the process of making the program.

You program should output a single move in the modified long algebraic notation, indicating what move you want to make on that turn. The move must be valid. The program must output its move within y seconds, otherwise it will resign. If the program outputs anything other than a valid move, it will be counted as a resignation.

Entering

To enter, submit an answer with the following information:

  • The name of the bot (to be used for score tables, etc.)
  • The language the bot is written in
  • The command line command needed to run the bot

If I cannot include your bot for any reason, I will add a comment explaining why I cannot. I will endeavour to install any programs required to run your bot, as long as it is legally free to access (sorry Mathematica people).

The final round will occur on xxxx/xx/xx. It is a round robin. Each bot plays against each other bot two times - once as black, and once as white. If a bot wins both rounds, it gains 1 point. If it wins one round, it gains 0.5 points. If it doesn't win either, it gains 0 points. The bot with the most points gets the green checkmark.

I will also hold regular practice rounds, of which you may find the results of here. The last practice round was held on xxxx/xx/xx. These practice rounds will continue even after the final round has finished.

Questions

  • Is the explanation of Chad's rules clear?
  • What would be good values for x and y?
  • Would the extra information in the input be helpful?
  • Any other advice would be appreciated.

I haven't written the control program yet. I intend on getting the specification ironed out first.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm sad to see this sort of thing here rather than elsewhere where it might find more long term interest. \$\endgroup\$ – Sparr Sep 11 '14 at 3:52
  • \$\begingroup\$ I strongly suggest that before posting to live you set up a github repo with the control framework, a sample bot, and a build script which builds all of the bots. See github.com/pjt33/ppcg36515 . I also have a suggestion which I've been mulling over with respect to koth in general: round robin emphasises the metagame over actual good play. How about having round robin for seeding purposes followed by a best-of-5 knock-out bracket? \$\endgroup\$ – Peter Taylor Sep 11 '14 at 9:16
  • \$\begingroup\$ ​​​​​​​​​​​​​​​@PeterTaylor When I finish the control framework I'll put it in a github repo. A tournament bracket sounds interesting - I'll try it on this KOTH and we'll see how it goes. \$\endgroup\$ – absinthe Sep 11 '14 at 9:28
  • \$\begingroup\$ Hi, this seems like a fun KOTH challengw. Is it still in the works? \$\endgroup\$ – AndoDaan Sep 21 '14 at 5:51
  • 1
    \$\begingroup\$ @AndoDaan Yes it is. I'm still writing the control framework. The problem was that before writing the challenge I didn't actually know how to program, so ​​​​​​​​​​​​​​​I have to learn how to program before I can make the control framework. \$\endgroup\$ – absinthe Sep 21 '14 at 6:04
  • \$\begingroup\$ Cool. Big task to start in, but I can imagine you'll get to know all the nooks and crannies of your 1st language. Have fun, and don't get disheartened! \$\endgroup\$ – AndoDaan Sep 21 '14 at 6:18

You must log in to answer this question.

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