How does the sandbox work, and how do I use it?

The sandbox works best if you sort the posts by "active".

See the sandbox FAQ for more information on how to use this sandbox.

Submission Directory

This is a community-maintained list of the most active submissions in the Sandbox. If you add a new submission to the sandbox, add an entry to the top of this list. You may also include a [status] indicator and tags to categorize your submission.

If you have an active submission which is not on the list, then you can add it. If this list grows too long, then you may remove entries on this list which have been inactive for several days.

code-golf

king-of-the-hill

others

share

443 Answers 443

Design and Solve a Maze

(this question on hold while the details are ironed out)


Your task is to play the roles of both characters in this scene from Inception. In it, Cobb gives Ariadne a challenge:

You have two minutes to design a maze that takes one minute to solve.

Some liberties will be taken on that description. Most importantly, this challenge is not time-based, rather scores are based on the effectiveness of your mazes and maze-solvers.

I apologize for the many edits to this challenge as we iterate towards an easy and fair format..

Part I: Maze format

All mazes are square. A cell in the maze is represented as a zero-indexed tuple row column.

Walls are represented by two binary strings: one for horizontal walls (which block movement between rows) and vertical walls (vice versa). On an NxN maze, there are Nx(N-1) possible walls of each type. Let's take a 3x3 example where the cells are labelled:

A   B | C
   ---
D | E   F
   ---
G   H | I

all possible vertical walls are: AB BC DE EF GH HI. Translated into a string, the walls shown are 011001 for vertical walls and 010010 for horizontal walls. Also, by "binary string" I mean "the characters '0' and '1'".

The full maze format is a string which contains, in this order:

  • width
  • start cell tuple
  • end cell tuple
  • horizontal walls
  • vertical walls

For example, this maze:

   0 1 2 3 4
   _________
0 | |  E|  _|
1 |  _|_|_  |
2 |_ _ _  | |
3 |  _ _  | |
4 |____S|___|
start:(4,2)
end:(0,2)

is formatted to this:

5
4 2
0 2
00001011101110001100
10100110000100010010

Part II: The Architect

The Architect program creates the maze. It must play by the rules and provide a valid maze (one where a solution exists, and the end is not on top of the start).

input via stdin: Two positive integers:

size [random seed]

Where size will be in [15, 50]. You are encouraged to make use of the random seed so that matches can be replayed, although it is not required.

output to stdout: A valid size x size (square) maze using the format described in Part I. "valid" means that a solution exists, and the start cell is not equal to the end cell.

The score of an Architect on a given maze is

   # steps taken to solve
------------------------------
max(dist(start,end),(# walls))

So architects are rewarded for complex mazes, but penalized for each wall built (this is a substitute for Ariadne's time restriction). The dist() function ensures that a maze with no walls does not get an infinite score. The outside borders of the maze do not contribute to the wall count.

Part III: The Solver

The Solver attempts to solve mazes generated by others' architects. There is a sort of fog-of-war: only walls adjacent to visited cells are included (all others are replaced with '?')

input via stdin: the same maze format, but with '?' where walls are unknown, an extra line for the current location, and a comma-separated list of valid choices from this location. (This is a big edit that is meant to make it simpler to write a maze-parsing function)

example (same as the above 5x5 maze after taking one step left)

5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2

Which corresponds something like this, where ? is fog:

   0 1 2 3 4
   _________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|

output to stdout: One of the tuples from the list of valid choices

Each Solver's score is the inverse of the Architect's score.

Part IV: King of the Hill

Architects and Solvers are given separate scores, so there could potentially be two winners.

Each pair of architects and solvers will have many chances to outwit each other. Scores will be averaged over all tests and opponents. Contrary to code golf conventions, highest average score wins!

I intend for this to be ongoing, but I can't guarantee continued testing forever! Let's say for now that a winner will be declared in one week.

Part V: Testing

I have written a Python testing kit which includes a Maze class for parsing and writing in the proper formats, as well as an example architect/solver pair: Daedalus and the Minotaur

Available on both Dropbox and GitHub

Part VI: Submitting

  • I maintain veto power over all submissions - cleverness is encouraged, but not if it breaks the competition or my computer! (If I can't tell what your code does, I will probably veto it)
  • Come up with a name for your Architect/Solver pair. Post your code along with instructions on how to run it.
share

md5sum Rainbow Table

This is my first code golf challenge; critiquing welcome.

Your task is to create a rainbow table of md5sum'ed integers. You need to output to STDOUT the integer, a space or a tab character, the md5sum, then a new line. The spec for an md5sum can be found here, thanks to the IETF. For example:

1 c4ca4238a0b923820dcc509a6f75849b
2 c81e728d9d4c2f636f067f89cc14862c
... 
//hashes generated on http://www.md5.cz/
  • You need to write the full program, not just the function.
  • You may use existing libraries so long as you are not directly calling an md5sum function from within that library.
  • Output is not case sensitive (A is the same as a when it comes to an md5sum).
  • You need to get all positive unsigned 32-bit integers from 1 to 4,294,967,295. You may load the numbers however you want into the program. You should input the integer as a string (i.e. using the ASCII code for each digit)
  • No downloading data from the Internet.
  • Code Golf, so the shortest answer wins!
share
1  
what should the output file be called? isn't it easier to use STDOUT? and should the character separating the number and its md5 be a tab or a space or the correct number of spaces? –  professorfish May 30 at 6:40

Recover a bzip2 file

Posted

share

Find the mines!

Tags:

You are a mine remover. Your job is to find all mines on a field, without a mine explodes. So, you write an application that can find the mines carefully.

The input

The input can either be provided through command line arguments or through STDIN (tell what you use in your submission). The input items are separated by commas.

The input looks like this:

<current step (zero-based)>,<mine count>,<field width>,<field height>,<field data>

The field data is like a Minesweeper field. Rows in the field data are separated by semicolons, columns are separated by nothing, as each column is just one character. Here are the characters you can get:

  • X This means that you don't yet know what's there, the real data is still hidden. At the start, you get a field full of Xs.
  • / This means that there is nothing on that location.
  • <number> Specifies the count of mines around the location of the number.
  • F This is marked by a flag by you.
  • ? This got a question mark from you. There might be a mine on it, but you are not sure. This is just used as a reminder for you, it doesn't mean something specific to the controller.

Example input:

2,1,3,3,XX1;X1X;XXX

That input means that it's currently your third step, there is one mine, the field is 3x3, and the field looks like:

X X 1
X 1 X
X X X

The output

The output consists of 4 parts: the X of which you want to see the data (like a click in Minesweeper), the location on which you want to put a flag mark, the location on which you want to put a question mark and a sign, used to let the controller know whether you are finished or not (0 for not finished, 1 for finished). Locations are written as X;Y, zero-based. If there is something you don't want to do, output -1. You can also remove flags/question marks using the same way.

Example output:

4;3,-1,3;3

Specifications

  • If your first output data is the location of a mine, you hit the mine and you die, but you'll still get a score.
  • If you select a X which hides an empty location (/), all adjacent empty fields (and their borders, which are numbers) will be revealed.
  • For every step, your program is executed again with the updated arguments.
  • When looking for mines, you are allowed to have more flags than the amount of mines. Only if you finish, the amount of flags must not be more than the amount of mines. If the amount of flags is greater than the amount of mines, your submission is disqualified (for every test!) and excluded from the scoreboard.

Testing

When I test your submission, I'll run 100 tests on every submission, with randomly generated fields, which I created using a program that I'll write after I got some feedback. Every submission gets the same test fields, so it's fair. Test fields look like this:

  • 10 tests with a 10x10 field and 10 mines.
  • 10 tests with a 10x10 field and 12 mines.
  • 10 tests with a 12x12 field and 14 mines.
  • 10 tests with a 15x10 field and 16 mines.
  • 10 tests with a 15x15 field and 35 mines.
  • 10 tests with a 20x20 field and 40 mines.
  • 10 tests with a 25x25 field and 50 mines.
  • 10 tests with a 25x25 field and 60 mines.
  • 10 tests with a 50x50 field and 100 mines.
  • 10 tests with a 50x50 field and 125 mines.

Scoring

You get 10 points for every mine you find, you lose 5 points if you think there is a mine somewhere when there is none and you lose 2 points for every mine you missed. The scoring is always the same, it doesn't matter whether you finish or die. The highest score wins.

In case of a tie, the count of steps is a tie breaker.

Controller

I'll start working on this after I got some feedback.

share
1  
You say "like Minesweeper" a couple of times, but on a cursory read I didn't see anything which differentiates it from Minesweeper. Why is this not a dupe of codegolf.stackexchange.com/q/24118/194 ? –  Peter Taylor Jul 24 at 14:58

Inspired by lifecompetes.com

Multiplayer Game of Life (GOL)

There are n players that play the Game of Life (standard rules) on an 50 x 50 grid. (Size, border conditions? Toroidal, Absorbing, Mirroring?)

Before first GOL-Step

When the game starts, each player has 12 cells that he can place anywhere he want as long as they do not overlap. Before the first GOL-step occures every player has to place 6 cells. If two players place their cell on the same spot no cell wil be placed an thei cells will remain in each players bank.

During game

In each GOL-Step, each player can place as many new cell on the grid as he has in his bank. If two or more players want to place a cell on the same spot, no cell will be placed there (the cells will remain in each players bank). Every six GOL-steps all the players who have less that 12 cells in their bank will get a new cell in their bank.

Goal

The goal is achieving the maximum number of cells on the grid during 1000 GOL-steps.

How to participate

Each participant has to write a javascript function of the following form (multiple return statements allowed.)

function my_bots_name(field, bank, golstep){
  /* your code */
  return p;
}

Where p is a 2d array of points [[x1,y1],[x2,y2],[x3,y3],...] that the player wants to set. field contains a 2d array of the GOL grid, bank indicates the number of cells in the player's bank, and golstep is the index of the current GOL step (golstep == 0 before the first GOL-step occurs). The function may not the global variables and cannot access Math.random() or Date(). In field the empty cells will be set to 0, the own cells will be set to 2 and the other player's cells will be set to 1. (You will not be able to distinguish between various other players.)

The winner will be determined with a game that contains all valid submissions after one week after the first submission.

TODO

The exact environment will be provided so everyone can test the own function before the official runs.

  • What size of the grid is appropriate? (dependent on number of players?)
  • How many steps should be computed?
  • What border conditions should be chosen?
  • Is the restriction of Math.random() and Date() apropriate? (The idea was that the games will be the same no matter of who/when they will be run. (Deterministic) )
share

The Painter's Predicament

This would be a question. This is my first question, so any guidance is appreciated.

A painter is commissioned to paint the outer wall of a house shaped as a regular n-gon, with walls 0 through n-1. Each one of these walls must be painted one of 26 colors, represented by the letters A through Z.

Thanks to the unstoppable forward march of technology, the painter has acquired a machine that can paint entire walls at once. The machine can move around the house, and can only have one color active at a time. This machine has 5 buttons. The buttons behave as follows:

Button #1 moves the entire machine to the wall to its left. 
Button #2 moves the entire machine to the wall to its right. 
Button #3 advances the current color forwards, so that A->B, B->C, and so on, until Z->A.
Button #4 is identical to Button #3, but instead moves the color backwards.
Button #5 paints the wall in front of it with the current color. 

When producing an estimate for a job, the painter would like to know how many buttons he'll have to press. Your task is to find that number for a given job.


Input

Input is given to you as a series of characters representing the desired coloring of the house.

For most, that will probably be a string, but you may accept them in whatever form is convenient for your language. If your language prefers them as a character array, from stdin, abandoned on the stack, or written straight into /dev/null, you may assume that as the input format.

Examples: ABCDEF, ZZZZZZ, and AAAAAC.

You may also choose to have the input be in the form of [n] [job], if that is more convenient for you desired input format.

Examples: 3 ABC, 10 QRSTUVFGHJ

You may not accept n as a separate piece of data. If you choose to have it be provided, it must be included in the input character series as specified.


Output

You must output the minimum number of button presses required to paint the entire house. This, again, may be done in whatever paradigm your language employs. Printing or returning the number are both definitely acceptable; the number must simply be made available to whomever invokes the code.


Additional Details

The house starts with all of its walls painted color A. If a job specifies that a wall must be painted A, it does not need to be repainted.

The machine starts at wall 0, with current color A.

n is at least 3.

share
1  
does the machine have to start with its color set to A? does it have to start off pointed at wall 0? –  Sparr Aug 5 at 23:57
1  
Some test cases would be good. –  Peter Taylor Aug 7 at 22:14

Balanced Ternary Converter

Background

Most of us are familiar with a few bases for numbers, like decimal, binary, hexadecimal, and octal. One interesting base is called balanced ternary. It has three digits and each place is multiplied by the corresponding power of three. What makes it interesting is that the digits are 1, 0, and -1 (often written as +, 0, and -).

Examples of Balanced Ternary

d4 => (1 x 3^1) +  (1 x 3^0) => t++
d2 => (1 x 3^1) + (-1 x 3^0) => t+-
d8 => (1 x 3^2) +  (0 x 3^1) + (-1 x 3^0) => t+0-

The Challenge

Write a program that can convert between decimal and balanced ternary. Your input will be a string of digits prefixed with either d or t. You must output the number in the other format, with the corresponding prefix. You can choose which characters you want for the balanced ternary digits (e.g. +0-, 10T). Negative decimal numbers are (as usual) prefixed with a -, but balanced ternary should not be; use the negative digit to make the correct number. You can assume numbers will fit in a 32 bit signed integer. Input can be a command line argument or STDIN, but the code should be a complete program.

Examples of Program Behavior

$ ./myprog d8
t+0-
$ ./myprog t+0-
d8
$ cat d-3 | ./myprog
t-0
$ cat t--+ | ./myprog
d-11

Scoring

Winner is the shortest program in bytes.

Sandbox Questions

Converting octal and hex numbers prefixed with o and h to ternary would be a cool add-on. What would be a reasonable byte reduction for that?

share
1  
Your example invocation shows the program taking input as a command-line argument, but the spec doesn't mention this. Is it acceptable to take input from stdin? The sentence beginning "Ternary numbers can be notated however you want" can seem to contradict the bit about prefixing with d or t, and might be better worded as "You can choose which characters to use for the balanced ternary digits". I think that having to handle negative input is good, but you might want to specify a range which must be handled (e.g. signed 32-bit integer). –  Peter Taylor Aug 7 at 22:22

Realistic Stock Market

This is based off of this other challenge, but with a whole lot of added realism. I'm trying to add as much realism as possible. It is a challenge.

You are an entrepreneur in the stock market, having created your own hedge fund (correct term?). Your company buys and sells shares in other companies, but also sells shares in itself.

At the very end of the game, the money is redistributed: All the money you've earned* is split up amongst your shareholders. Likewise, you gain money from the companies in which you've invested. By selling shares in yourself, there is a trade-off between long- and short-term gains.

There is a finite amount of each stock in the game, and there is one type of stock per company (so one per entrant). Your bot will start out with 100 shares of each other company, along with 100*N shares of itself, where N is the number of entrants. Each bot will have an initial bankroll of 10000 * N. (This helps to ensure a sufficiently large initial stock price).

Buying and Selling

Buying and selling stock is done by placing buy and sell orders. Each time a buy/sell order is placed, it is matched with the existing buy/sells orders to complete the trade.

Here is an example of how the orders are matched with each other for one stock:

 Before:
  Sell Orders:
   19 @ $20 - Bot A
   11 @ $21 - Bot B
  Buy Orders:
   06 @ $19 - Bot S #oldest is given preference 
   06 @ $19 - Bot Q
   13 @ $18 - Bot T
   22 @ $16 - Bot R

 New Order:
  Sell 26 @ $17 - Bot C
  Trades [06 @ $19 - Bot S] with a surplus of 20
  Trades [06 @ $19 - Bot Q] with a surplus of 14
  Trades [13 @ $18 - Bot T] with a surplus of 01
  No more matches

 After:
  Sell Orders:
   01 @ $17 - Bot C #the remainder of the sell order
   19 @ $20 - Bot A
   11 @ $21 - Bot B
  Buy Orders:
   22 @ $16 - Bot R

In this particular example, Bot C will manage to sell 26 shares for 12*19+13*18+1*17 = $479, assuming that someone will eventually buy that one remaining share. The bot receives $462 at the end of his turn, and would receive the $17 at the end of the buyer's turn. If the share is not bought in the time between one turn and the next, the bot would receive that remaining share back.

The Tournament Setup

The tournament will be composed of 10 games, with each game consisting of 365 trading rounds. Each trading round will consist of one turn for each bot, with the bots in a randomized order.

There is nothing special that happens between any particular round. This helps to smooth out game flow so that each bot will have equal opportunity on their turn.

At the end of each game, the money of each competitor is redistributed to its stock holders (how much of the money?).

The winner of the tournament will be the bot with the highest average amount of money at the end of each game.

A Single Turn

For each stock, the bot will receive the buy and sell orders available.

At the start of every bot's turn, that bot's previous unfulfilled sell/buy orders will be canceled. (Is this a good idea?). Any unsold stock or unspent money is returned to the player.

Then, the bot will output the list of buy/sell orders it would like to place. The bot will be able to place one buy/sell order per stock. The bot must be able to immediately set aside the shares/money to support the order.

The controller program will look through your sell and buy orders sequentially and will remove the assets from you that are required for the transaction. If you have insufficient funds, that order will be ignored completely.

Then, the orders will be processed. Orders that match the already-existing orders will allow the transaction to occur after the bot's turn. Orders that are unmatched will remain on the market until the start of the bot's next turn.

Recording the past

Your bot is allow to create 1 text file to maintain a history of stock prices.

Input

Input will consist of 3 arguments in this order:

Current round number, which is a number 1-365
Which stock ticker is for your company
A list of the data for each stock

The data for the stocks will be formatted like this:

"[stock ticker #1],[quantity 1],[price 1],[quantity 2],[price 2] [stock ticker #2],[quantity 1],[price 1],[quantity 2],[price 2]"

Each quantity/price pair represents one buy or sell order. Sell orders have positive quantity, while buy orders have negative quantity.

The order of the stocks will be randomized, but the stock tickers will remain consistent for the whole game.

(I was also think of including some more data in here, what else might be needed? Data on the assets of all the other competitors?)

Output:

Output will consist of many lines, each line formatted like so:

[stock number 1-N] [action] [quantity] [price]

The stock number is a number 1-N representing which stock to buy or sell. The action can be either b for buy or s for sell. The quantity and price can be any positive integer.


Notes:

I want price to have 2 decimal digits, but I don't know if that would exclude anything or make it unnecessarily complicated. Right now, the prices are limited to integers. There is approximately $50 for each stock in the game, in an attempt to increase smoothness.

We need to balance the number of actions allowed per turn with the number of rounds in a game. Right now, the player can make 1 order per stock in a single round, which may make the time flow too roughly. The more rounds played, and the fewer actions allowed per turn, the smoother the game will be.

*We need to determine exactly how the money is redistributed. I initially had the idea that all the money will be redistributed equally to each stock, so a player who sells all the shares in himself keeps none of the money he earned in game and only gets the money from the other stocks. I think it might make more sense to only distribute profits, but we would have to determine how much of the profits are redistributed to shareholders.

Is it a good idea to have orders cancel after a period of time? Currently, a bot's orders are cancelled upon that bot's next turn. If we reduce the number of moves per turn, then we would want to increase the longevity of the orders. Alternatively, we could make orders permanent and irrevocable, only being cancelled at the end of the game.

share
1  
The number of decimal places is largely irrelevant - a fixed number of decimal places is equivalent to integer. It's probably easier to model as integers internally, even if you display as 2 decimal places. You could just state that prices are in pennies/cents. –  githubphagocyte Aug 14 at 18:10
2  
I would recommend allowing orders to be placed and cancelled at any time. I don't think a restriction is necessary. What might make it more interesting is to introduce a cost to buying and/or selling. This should make strategy more important. –  githubphagocyte Aug 14 at 18:16
1  
I think that making each bot specify up front how much it will pay out in dividends would be good. It adds some asymmetry in round 1 (so it's not just picking a random share to buy). Probably do it in integer permille and round down when the time comes to distribute. It might even be interesting to make dividend payouts quarterly so that they don't just affect the final score. –  Peter Taylor Aug 14 at 19:43

Code with largest MD5 hash of output

Your code will output to STDOUT or save to a file. The output's MD5 hash will be taken and treated as an integer expressed in hexadecimal. If another answer posted before you gives the same MD5 hash then your answer is invalid.

The answer with the highest MD5 hash wins.

You can use whatever method you wish to prepare the output. Note that brute force might not be the only approach since MD5 is broken.

You will not use any hardcoded range narrowing unless based on a previous answer. That is, you can start a search from zero or you can start a search from a point determined from analysing a previous answer, which you will credit with a link to the answer. You are not restricted to lexicographic order of outputs when searching. For example you might choose to test all strings of the letter "a" up to a given length, followed by all strings of a letter "b". However, you cannot hardcode a string of length more than 1 to start the search from.

Your code must be deterministic. The output must be reproducible.

If you wish to use something from an answer posted after yours, you will have to post a new answer, so that the genealogy is clear.

To avoid portability problems, the output may not contain newlines of any type.

share
1  
This is just a kolmogorov-complexity question which changes as people find better outputs, and since the output is unlikely to have any nice structure there's a reasonable chance that the programs posted will just emit a literal string. It might be more interesting to add constraints that the first person to post a particular output has exclusive rights to it and to require the search program to be included in the answer. –  Peter Taylor Aug 15 at 16:34

Check GenericScript source code for compiler errors

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, the program should output "Invalid syntax", otherwise it should output "Valid syntax".

Win Criteria

This is code golf. Shortest code wins.

Syntax

Source code will be considered to be valid if it matches the rule for "Program" below.

Program             = Sequence
Sequence            = Statement [Sequence]
Statement           = SequenceBlock | Assignment | If | While | Output
SequenceBlock       = "{" Sequence "}"
Assignment          = Identifier "=" (String | Bool); 
If                  = "if(" Bool ")" Statement ["else" Statement]
While               = "while(" Bool ")" Statement
Output              = "print(" String ");"
Identifier          = {Any sequence of alphanumeric characters prefixed with "var" }
Bool                = StringEquals | Identifier
StringEquals        = String "==" String
String              = StringConstant | OperatorConcat | Input | Identifier
StringConstant      = "'"StringContent"'"
StringContent       = Character [StringContent]
Character           = {Any character except for "'"}
OperatorConcat      = String "&" String
Input               = "read()"

Whitespace is defined as any sequence of the ascii characters 9, 10, 13 and 32. Whitespace characters are allowed between tokens but are not required.

Rules

  1. The answer should be a complete program
  2. Standard input/output allowed
  3. Standard loopholes apply
  4. Universally testable answers only

Test Input

Valid syntax:

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

Invalid syntax:

if(read() == 'DoTask1')
  print('Executing you'r command');
share

Code Bots

The goal is to write a bot so viral that no other bot can resist but wave its flag.

You will have 24 lines of code to write your bot. Each turn, every bot will execute 1 line sequentially.

Each bot stores 5 variables A through E. A and B are for personal use, C stores the next line to execute, D stores the current direction, and E is a random number.

Each line must contain one of the following 5 commands:

  1. Flag does nothing. Except it's how you win
  2. Move moves your bot in the Dth direction. If a bot already occupies the space, no move will happen
  3. Copy Var1 Var2 copies the contents of Var1 into Var2
  4. If Condition Line1 Line2 If Condition is true, executes Line1, else Line2
  5. Block Var1 blocks the next write on a variable

A variable can be used as follows:

#Var will use the variable as a line number. If A is 17, Copy #8 #A will copy the contents of line 8 onto line 17. *Var will use the variable of your opponent. Copy 5 *C will set 5 to the opponent's C variable Var+Var will add the two variables. Copy D+1 D will rotate the bot to the right

When D is used as a direction, [North, East, South, West][D%4] will be used

These modifiers can be chained: Copy *#*C #9 will copy the next line your opponent will execute into your own code on line 9. **D refers to your opponent's opponent's D variable.

A Condition will be evaluated as follows:

  1. If Var:
    1. If Var is A through C, it will return true if Var is nonzero, else false.
    2. If Var is D, it will return true if there is a bot in the Dth direction, else false
    3. If Var is E, it will return true if E is odd, else false
    4. If Var is a line, it will return true if it is a Flag line
  2. If Var1 = Var2:
    1. Returns true if both are A-E, and equal the same number
    2. Returns true if both are D, and Var1%4 equals Var2%4
    3. Returns true if both are lines, and the line type is equal
  3. If Var1 == Var2:
    1. Returns true if both are A-E, and equal the same number
    2. Returns true if both are lines, and are identical (Flags from different bots will not be equal)

The bots will be placed in a toroidal world in the following pattern:

B...B...B...B...
..B...B...B...B.
B...B...B...B...
..B...B...B...B.

After 5000 turns, the flags on each bot will be counted. You get a point if a bot has more of your flag than any other type of flag. If the case of a tie between N bots, 1/N points will be given to each.

Side Notes

Attempting to do something that doesn't make sense, such as adding to a line will do nothing

Attempting to do something on a non-existent bot will do nothing

Infinite recursion on an If will end with no line being executed

If does not change the value of C

A Block doesn't expire until somebody attempts to write to it

Multiple variables and lines can be blocked at once

Blocking a variable multiple times will only block the next write

share

Render the Utah Teapot

[Hasty first posting.] [Revised and Posted]

The Utah Teapot, originally created by Martin Newell, is a convenient object for testing 3D graphics programs. Using the dataset available here (direct link, just the teapot), render a 3D view of the teapot (a perspective projection to 2D) with a simple lighting model (single light-source).

"Beige"

Requirements

snip! (see revisions for example postscript code).
I'm snipping for brevity, but I'm keeping the picture. :P and this note explaining it. And some other stuff up there.

share
1  
Bézier patches can be polygonised with the bounding box property and the de Casteljau algorithm. –  Peter Taylor Jan 28 '13 at 14:12

Display a Magic Square

Edit: Now proposing to instead add bounty to Magic Square Generator, which this is a dupe of. Please see comment and give feedback.


Your challenge is to display an n*n magic square of a given odd size n. A magic square is a grid of numbers in which each number 1,..,n^2 appears exactly once, and in which every row, column, and diagonal has the same sum.

A 5x5 Magic Square

Your program should be able to produce a magic square for any given odd number n with 2<n<32. Think of the parameter n as an input. Your may have your program get this value pre-initialized in a variable, as function input, passed from stdin, or starting on the stack.

Fewest bytes wins.

Any magic square that fits the conditions is fine. You don't have to find or verify that it's a magic square. See the Wikipedia article and Mathworld page for structured methods to make magic squares.

The program should display or print a magic square when run. Just returning it from a function or storing it in a variable is not sufficient.

The result must look like a 2D array of numbers. A list of entries printed on a single is not acceptable, nor is each entries on its own line. You can't rely on a fixed line width, but assume it's large enough to fit the square. The numbers must be somehow separated, since otherwise digits blend together, but any delimiter is fine.

There's no time limit to generate the output. If you want to brute-force search every grid until you find a magic square, that's fine even if won't output this century.

Standard loopholes apply. Functions that specifically generate magic squares are not allowed.

Example output with n=7:

1 2 47 46 33 30 16
11 45 35 18 24 14 28
44 38 9 13 19 23 29
42 7 10 25 40 43 8
21 27 31 37 41 12 6
22 36 26 32 15 5 39
34 20 17 4 3 48 49

Example output with n=13:

[[12, 169, 144, 132, 120, 108, 96, 84, 72, 60, 48, 36, 24],
 [27, 15, 3, 160, 148, 136, 124, 112, 100, 88, 76, 64, 52],
 [55, 43, 31, 19, 7, 164, 152, 140, 128, 116, 104, 79, 67],
 [83, 71, 59, 47, 35, 23, 11, 168, 156, 131, 119, 107, 95],
 [111, 99, 87, 75, 63, 51, 39, 14, 2, 159, 147, 135, 123],
 [139, 127, 115, 103, 91, 66, 54, 42, 30, 18, 6, 163, 151],
 [167, 155, 143, 118, 106, 94, 82, 70, 58, 46, 34, 22, 10],
 [26, 1, 158, 146, 134, 122, 110, 98, 86, 74, 62, 50, 38],
 [41, 29, 17, 5, 162, 150, 138, 126, 114, 102, 90, 78, 53],
 [69, 57, 45, 33, 21, 9, 166, 154, 142, 130, 105, 93, 81],
 [97, 85, 73, 61, 49, 37, 25, 13, 157, 145, 133, 121, 109],
 [125, 113, 101, 89, 77, 65, 40, 28, 16, 4, 161, 149, 137],
 [153, 141, 129, 117, 92, 80, 68, 56, 44, 32, 20, 8, 165]]
share
1  
@Geobits Hmm, that's too bad, that's what I get for not searching. Though the question is old and got few answers -- maybe I can justify reviving it? –  xnor Aug 23 at 2:26

Old fashioned intelligence gathering

As we've heard in the news, some intelligence agencies have decided to go back to typewriters due to the security hazards of the Internet. You are a spy. In spite of this change in policy to make messages more secure, one of your contacts scores an intelligence treasure trove: rolls of spent typewriter tape from your enemy.

The only problem? Whomever your enemy spy agency hired was a really bad typist. In fact, they tended to hit as many wrong keys as they did write. So when you read out the first bit of tape, you see

DQSIRINKSFIJATOAPQFFOUSJAR

Yikes. That's some attrocious typing. Seriously, there's training tools for that. Anyways, you're in luck. You also scored the correction tape:

QSIFIJOAPQFSJA

After racking your brain for hours, you realize someone just wanted some booze:

DQSIRINKSFIJATOAPQFFOUSJAR  (ink tape)
-QSI-----FIJ--OAPQF---SJA-  (correction tape)
D---RINKS---AT-----FOU---R  
DRINKS AT FOUR              (message)

There's a lot of tape though, and you know there's some good intelligence information here, so you write an program to determine the original messages after filtering out the massive amounts of typos.

Rules

Input

  • a return-delimited dictionary file
  • ink tape letters (all caps)
  • correction tape letters (all caps)

Output

  • all possible original messages ordered from fewest to most words in message; there shall be no specified ordered for messages with the same number of words. If the intended message were MY GRANDMOTHER HAS A LIFELONG PASSPORT, the output should generate the following (going from 6 words to 9 words):
    • MY GRANDMOTHER HAS A LIFELONG PASSPORT
      MY GRAND MOTHER HAS A LIFELONG PASSPORT
      MY GRANDMOTHER HAS A LIFE LONG PASSPORT
      MY GRANDMOTHER HAS A LIFELONG PASS PORT
      MY GRAND MOTHER HAS A LIFE LONG PASSPORT
      MY GRAND MOTHER HAS A LIFELONG PASS PORT
      MY GRANDMOTHER HAS A LIFE LONG PASS PORT
      MY GRAND MOTHER HAS A LIFE LONG PASS PORT

Other notes

  • all words in the original message will be spelled correctly (the typist was terrible, but they worked hard to eventually craft a correct sentence).
  • you may precapitalize your dictionary
  • all messages are alpha only (no numbers or punctuation)

Scoring:

  • Code golf, shortest code wins.

Additional sample tapes your assistant decoded to use to test your algorithm:

NUAFCLEAIEOJRWARWESHEADAJIOWGUNDSUIVHERCSNZXAPITASAOIDLBUIJOVEMOLDINGIAS (ink tape)
AFIEOJWESAJIOWGSUIVHSNZXSAOIDJOVEMOIAS (correction tape)
NUCLEAR WARHEAD UNDER CAPITAL BUILDING  (decoded messages)
NUCLEAR WAR HEAD UNDER CAPITAL BUILDING 

ASSLEDELPERIWECERSPDLLSACFSPTIVVOXATEIQPTREOIOSJFNMORROAIOW (ink tape)
ASDLIWERSPDFSPVOXIQPREOISJFNOAI (correction tape)
SLEEPER CELLS ACTIVATE TOMORROW (decoded messages)
SLEEPER CELLS ACTIVATE TO MORROW

ASOIIJHAWQRATEMSDQPOYJKWEOABS (ink tape)
ASOIJWQRASDQPOKWEAS (correction tape)
I HATE MY JOB (decoded message)
share

Implement elliptic curve Diffie-Hellman

Although the reputation of elliptic curves in general took a hit in 2013 due to suspicions that the NSA may have backdoored the parameter values of the common standard curves, Dan Bernstein's Curve25519 appears to be free of those suspicions. It therefore seems like the correct choice for an ECC codegolf challenge.

Implement a function (or procedure, named verb, or named block as appropriate to your language of choice) which performs the core curve25519 operation. Full details are provided in the linked PDF, and an alternative explanation is provided in a draft IETF RFC.

The function definition uses a 32-octet datatype for two inputs and one output; for this purpose you may choose to use an array of bytes, a 32-character ASCII string, or a base-16 representation, but not an arbitrary-precision integer type. You may, however, use arbitrary-precision integers internally. You may give the output via an out param, as in the reference implementation, or as the return value.

TODO Test vectors. NaCl has a couple, probably need to invent a couple more.


Specific requests for feedback:

  • How much of the detail of the function definition should I inline? The elliptic curve group action? An overview of finite fields?
  • Does anyone have strong opinions on allowing arbitrary-precision integer input and output? This would tend to favour those scripting languages which have the datatype for free.
share

Unhappy numbers ascii art

Draw a square (or a rectangle as close to a square as possible) that represents the cycle of an unhappy number.

[ short description of unhappy numbers here + example ]

[ square formating rules ]

Input: unhappy integer

Output: ascii art

example:

input: 4
output:
 4 -  16 - 37 
20         58
42 - 145 - 89
share

Generate a Texting Dictionary

Old fashioned cell phones were and are used heavily as texting platforms, unfortunately the keyboard has only 12 + a few buttons, and is therefor ill-suited to naive text entry.

Common solutions make use of the traditional telephone coding (generally with a modest extension for 'q' and 'z'):

2: a,b,c
3: d,e,f
4: g,h,i
5: j,k,l
6: m,n,o
7: p(,q),r,s
8: t,u,v
9: w,x,y(,z)

In this case we are interested in the one-press-per-letter schemes that offer up words matching words on a frequency basis. That is if the user type "4663" the phone will offer up words like "good", "home", "gone", "hood", "hoof", etc that code to 4663 in order of their frequency.

Your task is to read one or more input files and generate a frequency sorted dictionary that could be used to implement this scheme.

Inputs

  • All input will be plain ASCII text.
  • You may accept input from named files, the standard input, or other conventional source supported by your implementation language, but there must be some mechanism to process several files in a single run.
  • Non-letter, non-whitespace characters should be stripped from the input, this means that contractions will be coded without their apostrophe: "don't" --> "dont" --> 3668
  • Words are a sequence of letters separated surrounded by whitespace
  • All whitespace (space, tab, newline, beginning-of-file, end-of-file) is equivalent.

Output

  • The output consists of a ASCII text stream
  • You may direct this to a file, the standard output, or any other conventional destination supported by your implementation language
  • The output should consist of one line for each string of digits corresponding to at least one word in the input.
  • Each line should consist of the digit string and a list of all corresponding words sorted by frequency with the most frequent coming first. A sample line of output would be

    4663 good home gone hood hoof
    
  • Tokens (digit strings and corresponding words) should be separated by a single space.

  • Equally frequent words may be sorted in any order.

Test Case and Validation

[Still to come. The test case will contain no frequency ties to ease the evaluation]

Tags

share
1  
You don't indicate if we'd and wed both appear in the input if they should both appear in the output, or is only wed acceptable? (I suspect they should both appear.) In otherwords, be clear that stripping non alphabetics (as well as casefolding?) is only for the purpose of bucketing into the numeric key sequence, not for printing the final dictionary, nor for counting frequency. –  MtnViewMark Jun 1 '11 at 6:44

I want to clarify this and post this question again.

Expanding Expressions [Posted]

Given an expression of one-letter variables ([a-z]), operators (*, +, &) and parenthesis, expand it using the following axioms:

a * b != b * a
a * b * c = (a * b) * c = a * (b * c)
a + b = b + a
a + b + c = (a + b) + c = a + (b + c)
a * (b + c) = a * b + a * c
a & b = b & a
a & (b + c) = a & b + a & c

   | Comm | Assoc | Dist
 * | NO   | YES   |     
 + | YES  | YES   | *    
 & | YES  | YES   | + *  

The user will input an expression, the syntax of the input expression is called "input form". It has the following grammar:

inputform ::= expr
var ::= [a-z] // one lowercase alphabet
expr ::= add
       | add & expr
add ::= mult
      | mult + add
mult ::= prim
       | prim * mult
       | prim mult
prim ::= var
       | ( expr )

Before That means, the order of operations is * + &, a + b * c & d + e = (a + (b * c)) & (d + e) Furthermore, the operator * can be omitted: a b (c + d) = ab(c + d) = a * b * (c + d)

Whitespace is stripped out before parsing.

Examples:

(a + b) * (c + d)
= (a + b)(c + d)
= (a + b)c + (a + b)d
= ac + bc + ad + bd
(a & b)(c & d)
= ac & ad & bc & bd
(a & b) + (c & d)
= a + c & a + d & b + c & b + d
((a & b) + c)(d + e)
= ((a & b) + c)d + ((a & b) + c)e (I'm choosing the reduction order that is shortest, but you don't need to)
= ((a & b)d + cd) + ((a & b)e + ce)
= ((ad & bd) + cd) + ((ae & be) + ce)
= (ad + cd & bd + cd) + (ae + ce & be + ce)
= ad + cd + ae + ce & ad + cd + be + ce & bd + cd + ae + ce & bd + cd + be + ce

Due to commutativity, order of some terms do not matter.

Your program will read an expression in input form, and expand the expression fully, and output the expanded expression in input form, with one space separating operators, and no spaces for multiplication. (a + bc instead of a+b * c or a + b * c or a + b c)

The fully expanded form can be written without any parens, for example, a + b & a + c is fully expanded, because it has no parens, and a(b + c) is not.

Here is an example interactive session (notice the whitespaces in input)

$ expand
> a(b + c&d)
ab + ac & ab + ad
> x y * (wz)
xywz
> x-y+1
Syntax error
> c(a +b
Syntax error
share

The Game of Life

John Horton Conway's simulator The Game of Life is a very simple array-based program which simulates mono-cellular life via four simple rules.

  1. Any True cell with fewer than two True neighbors "dies" (becomes False), as if caused by under-population.
  2. Any True cell with two or three True neighbors "lives on" to the next generation.
  3. Any True cell with more than three True neighbours becomes False, as if by overcrowding.
  4. Any False cell with exactly three True neighbours becomes a True cell, as if by reproduction.

Your task, should you choose to accept it, is to golf an implementation of this simple game which adheres to the following specs.

Input


The game's initial state is entered via STDIN, with lines of this format

x,y\n

where x,y is a point with an initial Boolean value of 1 or True.

Entries should take the following input via argv

$ ./foo.bar X_size Y_size Itters
  • X_size is the world's X space [0,X_size-1]
  • Y_size is the world's Y space [0,Y_size-1]

*All game activity will take place in the rectangle (0,0) (X_max,Y_max)*

  • Itters is the number of clock ticks the simulation should pass before printing the world

Output


The output will be of the same format as the STDIN input, a newline-delimited list of points which are "True" at the end of the simulation.

NOTE: the order in which the points are printed is irrelevant.


Test Cases

Case 1
Input: $./foo.bar 3 3 2
     1,0
     1,1
     1,2
Output:
     1,0
     1,1
     1,2

Case 2
Input: $./foo.bar 6 6 1
     1,3
     1,4
     2,4
     3,1
     4,1
     4,2
Output:
     1,3
     1,4
     2,4
     3,1
     4,1
     4,2
     3,2
     2,3

share

Perfect Hash Generator

Given N words you are to generate a perfect hash function (ala gperf). A perfect hash function for a set of strings is a hash function with no collisions. An additional condition is that the range of the generated hash function must be [0...O(N)] (i.e. at most a constant times larger than N). You can use any language for the generated function.

share

You must log in to answer this question.

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