What is the Sandbox?

This "Sandbox" is a place where Programming Puzzles & 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 and click "Answer This Question". Give the details of your challenge just as you would when actually posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, and mark it as posted here.

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

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

Submission Directory

This is a community-maintained list of the most active Sandbox submissions, sorted by major contest type. Add an entry to the top of this list if you add a new submission or update an old one. If you don't have enough reputation to edit questions you can ask in chat for a higher-rep user to add your submission for you. You may include a [status] indicator and tags to categorize your submission.

If this list grows too long you may remove entries that have been inactive for several days. It's best to remove submissions from this list once they've been posted to the main page.

code-golf

king-of-the-hill

Others

share

544 Answers 544

Text Adventure Game

Objective

Your goal is to develop a complete text-based adventure game with the shortest code possible. The player navigates in a dungeon composed of rooms. The game objectives are to find the treasure, slain the dragon and rescue the princess.

Rules

A room description is as follows:

You are in <description>.
You can go <exits>
You see <object>      (optional)
  • exits can be "north", "east", "west", "south".
  • description can be "a adjective cavern", "a adjective room", "a adjective corridor", "a adjective hall", "a cell", "the dragon's lair".
  • adjective can be "dark", "murky", "small", "large", "narrow", "gloomy", "huge", "strange", "tiny", "broad", "old".
  • object can be "the princess", "the dragon", "a troll", "a goblin", "a sword", "gold", "a key", "a trunk".

Exit list must be comma-separated and end with "and". If there is no object in the room, the last line is omitted.

Example of valid description:

You are in a murky room.
You can go north, east and south.
You see a goblin.

The game accepts the following commands (case is ignored) :

  • GO direction : direction can be NORTH, EAST, WEST, SOUTH
  • TAKE item : item can be SWORD, GOLD, KEY
  • KILL monster : monster can be DRAGON, TROLL, GOBLIN. The DRAGON and the TROLL can be killed only if the user has the SWORD. If he hasn't, he loses the game. The weak GOBLIN can be killed with bare hands. When a monster dies, he disappears from the room. When the GOBLIN dies, he drops a SWORD. When the TROLL dies, he drops a KEY.
  • KISS person : person can be PRINCESS, DRAGON, TROLL, GOBLIN. Kissing the princess validates one of the objective of the game, and the princess disappears from the room. Kissing a monster results in player death.
  • OPEN object : object can be TRUNK. If the player has the KEY, the TRUNK object disappears and is replaced with GOLD.

OBJECTS
The player can perform an action on an object only if the object is in current room. A room can contain only one object ; a given object can be found in only one room. At the beginning of the game, only the following objects are placed in the map : PRINCESS, DRAGON, TROLL, GOBLIN, TRUNK. Other objects are not yet created.

ACTIONS

  • If an action cannot be performed (e.g. GO NORTH where there is no exit to the north, or TAKE DRAGON, or DANCE GANGNAM STYLE), the message "Sorry, I can't do that" must be displayed.
  • If an action can be performed, the message "OK" and the current room description should be displayed.
  • You can read game commands from console or as a program parameter, as you wish.

MAP
The dungeon should have at least 30 rooms. The dungeon should not contains a series of more than 5 exits in the same direction. The exits between rooms must be consistent, e.g. if you go north from room #1 to room #2, there must a south exit in room #2 leading back to room #1. Every room name should be unique. There must be at least one room of each kind (hall, cavern, corridor...)

  • A hall has at least 3 exits.
  • A corridor can have only 2 exits.
  • The cell has only one exit.
  • There is only one dragon's lair and only one cell, containing respectively the dragon and the princess.

GAME END
The game ends when the player has been killed, or when he has taken the gold, slain the dragon and kissed the princess.

  • If the player dies, the message "You have been killed by X !" is displayed, with X being the name of the monster.
  • If the player wins, the message "Well done adventurer ! you've conquered the dungeon." is displayed.

Player should not be able to win the game in less than 40 turns.

Example

You are in a murky room.
You can go north, east and south.
You see a goblin.
> KILL GOBLIN
Ok.
You are in a murky room.
You can go north, east and south.
You see a sword.
> TAKE SWORD
Ok.
You are in a murky room.
You can go north, east and south.
> GO NORTH
Ok.
You are in a narrow corridor.
You can go south and east.  

Scoring

The shortest code wins.

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

Marvelous Moonglyphs: Match Kana To Kanji

enter image description hereenter image description here

For people who are curious, like to do research, and want to learn something new.

This is a somewhat real-world example that isn't to hard to implement, but it may seem difficult because many people around here won't be familiar with the topic.

Overview

Recently your company started to expand its business to the Asian market. Nobody volunteered, so you have been asked to come up with some Japanese text processing code. Japanese addresses often come as a bunch of squiggly moon-glyphs, with the prefecture, district, and town name all mangled together. On the net, you found a list that tells you how to read that bunch, but you (and your Japanese customers) would like to know how to pronounce the district and town name by itself.

A very brief, over-simplified explanation of the Japanese writing system:

Japanese consists 100~200 syllables. They can be written with 48 kana, similar to our alphabet. There are two versions, Hiragana and Katakana, like lowercase and uppercase letters. Kanas are like a phonetic transcription. A word can also be written with meaning-based kanji. Each kanji may possess multiple readings. Given a word with many Kanji and its reading in Kana, determine which Kanas belong to which Kanji. Look up Kanji on wikipedia if you want to know more.

All Hiraganas ["lower case"] are

がぎぐげござじずぜぞだぢづでどばびぶべぼぱぴぷぺぽあいうえおかきくけこさしすせそたちつてとなにぬねのはひふへほまみむめもやゆよらりるれろわをんぁぃぅぇぉゃゅょっゐゑゔ

And the Katakanas ["upper case"] are

ガギグゲゴザジズゼゾダヂヅデドバビブベボパピプペポアイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲンァィゥェォャュョッヰヱヴ

They correspond to each other in the order given above.

Scoring

Feature-challenge.

Your program should implement the basic feature described below. Your basic score is 20.

You will receive additional points for each feature you implement. In case of a tie, code length in bytes decides.

Disclaimer

Standard loopholes shall (not) apply.

First, I will provide you with the information needed to define the task.

After that, I shall add some notes, examples, and hints for those of you not familar with Japanese. If you want to challenge yourself, and do some research yourself, do not read this.

Task

It is your task to write a program that will take as its input a string of MOONGLYPHS, its READING, and the moonglyphs separated into PARTS whose readings your program should output. You already found a dictionary file with all possible readings for each MOONGLYPH. (see below). All examples are formatted as follows:

  • MOONGLYPHS
  • READING
  • PART1,PART2,PART3,...
  • EXPECTED_OUTPUT

A simple example:

  • 成田 [Narita, name of a town]
  • なりた [na-ri-ta]
  • ,
  • [,なり],[,]

The MOONGLYPHs 成田 are read なりた. The parts and are read なり and .

I/O source and destination

Up to you, as long as it a complete program, ie you may read from

  • a file
  • stdin
  • network
  • keyboard

Same for the output.

Input and output format

Input:

  • All strings may be encoded in the encoding of your choice. (eg UTF-8, Shift-JIS etc.)

  • MOONGLYPH and READING are strings (or an equivalent in the language of your choice).

  • PARTS are an array, or an equivalent data structure in the language of your choice. Each entry is a string.

  • MOONGLYPH only contains MOONGLYPHs found in the Dictionary File. (see below)

  • It may also include other characters, if your program implements the corresponding feature.

  • If you support all features, it may include KATAKANA, HIRAGANA, and various full-width symbols and punctuation marks as well.

  • It will never contain any half-width letters, numbers or marks. (such as ,.=?)agE234\)

  • READING only contains HIRAGANA.

  • If you implement the corresponding feature, it may contain the same full-width symbols and numbers that MOONGLYPHs may contain.

  • The array of PARTs, when joined in the given order, will result in MOONGLYPH. For example, if MOONGLYPH is 日本語, then parts may be [日本,語] or [日,本,語] - but not [語,本,日] (reversed order) or [日本] (missing 語).

Example:

  • 日本語 (Japanese)
  • にほんご [ni-hon-go]
  • 日本,

The MOONGLYPH string is 日本語, the READING is にほんご, and the parts are 日本 and .

Output

  • An array, or equivalent data structure.

  • Each entry contains one of the input PARTS, as well as the corresponding part of the READING - in the same order as PARTS. Joining all parts results in MOONGLYPHs, and joining all readings results in the READING.

  • If there is no match, your program must behave in a way that is distinguishable from when it finds at least one match - including outputting nil, an empty array, or crashing.

Example:

  • 日本語 (Japanese)
  • にほんご
  • 日本,
  • [日本,にほん], [,]

All of the following cannot be valid outputs under any circumstances, irrespective of the dictionary data:

  • [,], [日本,にほん] (reversed order)

  • [日本,], [,] (joining the readings results in にご, which is not equal to the READING, にほんご)

  • [,にほん], [,] (joining the moongylphs results in 日語, which is not equal to the MOONGLYPHs, 日本語)

Dictionary File

The dictionary file is called KANJIDIC (not KANJDIC212) and can be found on this page (English):

It comes in a few different formats, choose one you like. Treat suffixes and prefixes as regular readings, strip the okurigana off the reading.

I also added the files on this github.


Basic Feature

Score = 20

Output the readings for each part, as described in the Input/Output section.

A somewhat longer example:

  • 京都府京都市下京区大黒町仏光寺通御幸町西入 [Kyoto, Shimo-Gyouku District, Daikoku]
  • きょうとふきょうとししもぎょうくだいこくちょうぶっこうじどおりごこまちにしいる
  • 京都府,京都市下京区,大黒町,仏光寺通御幸町西入
  • [京都府,きょうとふ], [京都市下京区,きょうとししもぎょうく], [大黒町,だいこくちょう], [仏光寺通御幸町西入,ぶっこうじどおりごこまちにしいる]

The only possible combination, given the dictionary data, is that きょうとふ belongs to 京都府, etc.


Optional Features.

No need to implement all features if you don't understand one of them. Remember, have fun.

壱 (1) +15

Implement Rendaku (Voicing). Handakuten count as voicing as well. No ヴ.

To keep it simple, we are going to assume that this voicing may always occur, except for the KANA at the beginning of the READING string.

  • 初霜月
  • はつ, しも, づき

弐 (2) +10

Support and ignore these punctuation symbols.

─〜、・()。!?「」/〒【】『』0123456789

These appear both in the MOONGLYPHs, READINGs, and PARTs at the same abstract position and should be ignored. That is, your program does not need to handle unmatched punctuation. You may assume that punctuation characters will always agree between MOONGLYPHS and READING.

  • 桜川市(亀岡) ["Cherry Flower River", "Turtle Hill"]
  • さくらかわし, (かめおか)

Invalid input:

  • 桜川市(亀岡)
  • さくらかわし, かめおか

参 (3) +10

Support , , and .

All three may be read and . and may also be read and .

肆 (4) +10

Support omitted genitive markers between MOONGLYPHS. An addtional +5 if you support as well.

  • 油小路
  • あぶらのこうじ
  • , 小路
  • [,あぶら], [<empty>,], [小路,こうじ]

伍 (5) +15

Support full-width roman numbers. You only need to support integers >0 and <1E12, and do not include any separators at any power of 10.

There shall be no before , , , and .

An addtional +5 if you support an optional before , , , and . That is, 102番 may be read either as 百番 or 一百番.

  • 12月
  • じゅうにがつ
  • 12,
  • [12,じゅうに], [,がつ]

陸 (6) +15

Add support for KANA. Including the now deprecated four , , , read as and `え.

, , will never appear as , , or in the output.

  • 岩月町かしわ野 [City of Iwatsuki "Moon Rock", Kashiwano "Evergreen Oak Plains"]
  • いわつきまち, かしわの

漆 (7) +5

Add the additional MOONGLYPHs found in KANJIDIC212. You can download it from the same page as KANJIDIC, see above. XML here.

  • 鱏八軟骨魚綱板鰓亜綱仁属為 (Batoidea are Chondrichthyes, Elasmobranchii)
  • えいはなんこつぎょこうばんさいあこうにぞくす

捌 (8) +10

Prefer on-on and kun-kun readings, and sort the results accordingly.

This requires a metric. To keep things simple, set the likelihood to zero, add +1 for each on/on or kun/kun pairs.

So for example,

  • ON ON KUN KUN => likelihood 2
  • ON KUN ON KUN => likelihood 0
  • ON ON ON KUN => likelihood 3

Punctuation symbols and KANA are be ignored for this calculation.

玖 (9) +15

Implement the MOONGLYPH doubler sign .

When the MOONGLYPH repeater 々 occurs m*n times, it may stand for the last n MOONGLYPHS occuring m times.

  • 月光綺麗々々々々々々 [The moonlight. Beautiful, beautiful, beautiful, beautiful.]
  • げっこうきれいきれいきれいきれい
  • 月光綺麗, 々々々々々々
  • [月光綺麗,げっこうきれい], [々々々々々々,きれいきれいきれい]

The input MOONGLYPHs shall never be such that any possible choice for n or m results in a previous occurence of 々 getting repeated. Thus, 木々日々々々 would not be a valid input.

拾 (10) +10

Support the voiced kana repeater . ひゞ shall stand for ひび or ひぴ, ごゞ for ごご, and ぱゞ for ぱば or ぱぱ.

It may not occur after syllables that do not accept dakuten, eg まゞ will is invalid input.

  • きゞ
  • きぎ

陰 (Final) +20

Support Ateji, Gikun readings, that is support multi-MOONGLYPH words.

Dictionary File EDict. Use either edict.gz or edict2.gz (custom format); or JMdict.gz or JMdict_e.gz (xml). The download page also contains links to the documentation of the dictionary format.

(1)

(2)

  • 独逸 [Germany]
  • どいつ

This word is found only in EDICT2, but not in EDICT.


Complex Example

This example requires features 1,2 5, and 9.

  • 173〜190番地「鉢伏峠」等々
  • ひゃくななじゅうさん〜いっぴゃくきゅうじゅうばんち「はちぶせとうげ」とうとう
  • 173〜190, 番地, 「鉢伏峠」, 等々
  • [173〜190,ひゃくななじゅうさん〜いっぴゃくきゅうじゅう], [番地,ばんち], [「鉢伏峠」,「はちぶせとうげ」], [等々,とうとう]

Tutorial

Do not read any further if you want to challenge yourself, or do the research yourself.

Moved here to keep this short.


May your journey to the moon be successful and fruitful, brave adventurer!

share
3  
@blutorange In the interest of people actually reading all of this, you might want to put the non-essential 2/3rds in a gist on GitHub and link to it. –  Martin Büttner Sep 2 at 10:10

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?
share
1  
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. –  Lembik Sep 9 at 12:51
1  
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? –  flawr Sep 10 at 9:49

The Best Way to Rake Leaves

[This is just a little problem I thought up while doing yard work today. It is not fully specified and I may not finish it if some simple optimal solution is found.]

Suppose some 2D grid represents the area of a lawn. A number of leaves are strewn over the lawn and they are modeled as single grid points. You have a rake that is modeled as a line segment of length L.

example

To start you can rotate the rake in any way and put it anywhere on the grid.

When the rake is moved some distance d along its perpendicular, all the leaves in its path are caught in it. They stay on the rake line until the rake stops (as with normal raking).

You repeat this process (moving the rake different distances every time) until all the leaves all lie on one singular point.

The question is: what is the minimum distance the rake has to move to make this happen?
(i.e. what is the minimum sum of the d's from each move?)

Challenge Spec (details incomplete)

Write a program that takes in a list of (x, y) leaf points and the length L of the rake (all floats).

The program should output a sequence of rake moves in the form of ((x1, y1), (x2, y2)) line segments that the rake travels perpendicularly down the center of. This sequence must bring all the leaves to the same exact point when they are "moved" by the rake

The challenge is to make an algorithm that does this with the least possible sum of sqrt((x1-x2)^2 + (y1-y2)^2) over all points.

[At this point several test cases would be given, with different L values and different leaf distributions. The submission that minimizes the total distance wins (assuming they do not hard code the answer).]

[This optimization problem does not seem to have any trivial solutions or even a clear optimal solution. Can anyone else poke holes in it?]

share

The Tetris Tournament

We've implemented Tetris before. But we haven't played it yet. So you're to write a bot which plays Tetris in real time!

The Rules

We're playing standard Tetris. That is, there will be one falling one-sided tetromino, which you can move and rotate until it hits the bottom. Complete lines of blocks get cleared, which causes all lines above to shift down accordingly. You will always be aware of the next tetromino. The goal is to clear as many lines as possible while the game gets faster.

Here are the specifics of rules which differ among various Tetris implementations:

The board will be 10 blocks wide and 22 blocks tall. The top two rows are "off-screen": tetrominoes will not spawn in the top two rows, but may be rotated into these.

The right-handed Nintendo Rotation System will be used (which is equivalent to the original rotation system). That is, each piece is basically in a square bounding box and cycles through 1 to 4 fixed patterns within that bounding box as given by this chart. Each tetromino will spawn in the first of its orientations such that its top-most blocks are in the top on-screen row, and the piece is centred horizontally (rounded to the left).

There is no wall kick or floor kick. If a rotation would lead to overlapping or out-of-bounds blocks, it will be ignored.

There is a lock delay equal to current step duration. That is, tetrominoes lock into place when the controller tries to move them down but hits another block or the floor.

The sequence of tetrominoes is determined by the Random Generator. That is, whenever the queue for pieces is empty, a random permutation of all 7 tetrominoes will be enqueued. I will add one exception to this: when the game starts, a random number of tetrominoes will be discarded from the first permutation, such that it's not immediately obvious where one ends and the next starts.

"Pressing" down does a soft drop. In particular, it will move the tetromino down one row without resetting the timer for the next drop due to gravity.

The game starts at level 0 and is incremented by 1 every 10 cleared lines.

Gravity will be such that tetrominoes move down one row every 0.1/(n+1) seconds, where n is the current level.

The game ends when a tetromino spawns overlapping an existing block or any blocked is locked into one of the two off-screen rows at the top.

There is no hold piece.

The Controller and the Bots

The controller will simulate the game in real time, and provide you with the game state whenever you request it (as well as when the game starts).

At any time, your bot can write a single-character command as one of [UDLRS] to STDOUT. The letters correspond to the following commands:

  • U(p): Rotate the current tetromino clockwise by 90 degrees. This will be ignored if the rotation would lead to a collision.
  • D(own): Move the current tetromino down a row. This may lock the current tetromino if moving it down would lead to a collision. In this case only will the timer be reset such that you get the full time for the next tetromino's first move. Otherwise the timer will continue where it was before.
  • L(eft): Move the current domino one column to the left.
  • R(ight): Move the current domino one column to the right.
  • S(tate): Request the current game state in STDIN.

Don't forget to flush STDOUT after sending any of these commands.

At the beginning of the game or if you send S the controller will write the game state to STDIN in the following format:

[seconds till gravity tick] [level] [lines cleared] [current tetromino] [next tetromino]
[10x22 representation of the board]

Where the tetrominoes are represented as a letter from [IOTJLSZ]. In the board representation, locked blocks are represented as #, currently falling blocks as * and empty tiles as ..

Your bot must not use more than 1GB of memory at any time.

Example

Here is a state from an actual Tetris game and how it would be represented by the controller:

enter image description here

0.0467896 1 16 J I
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..***.....
....*.....
..........
.......###
...#######
.#########
#######..#
#####.####

Scoring

We will use the Original Nintendo Scoring System: sending D gives you 1 point. Clearing lines gives you 40, 100, 300, 1200 points for 1, 2, 3, 4 lines, respectively. Points for clearing lines are multiplied by n+1 where n is the current level.

I will run each bot 10 (?) times and your final score will be maximum (?) achieved in any of those runs.

Sandbox notes

The controller still needs to be written, but I'd like the gather some general feedback regarding the spec (and how interesting the challenge is) first.

Along with the controller I'll provide a very stupid random bot to showcase how to set up the game loop with requesting the state from the controller.

Any suggestions about figuring out the overall score from the individual runs? I guess I can't determine the number of runs before I know how much scores fluctuate and how long one run takes. But what would make most sense statistically? Mean, median, maximum?

Let me know if anything else is unclear or could be improved!

share

Find the nth fraction - a code golf/code bowling challenge

Posted

share

Can you lose from this chess position?

Introduction

You are an arbiter who supervises a very large number of chess tournaments. Thus, you frequently rule on whether a player who runs out of time may claim a draw based on Article 6.9 of the FIDE Laws of Chess:

[...] If a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves.

In order to be able to perform your job more efficiently, you decide to create a computer program that determines whether it is possible for a player to be checkmated from a given position.

Regulations

The rules of the board game considered in this problem shall be identical to chess, except that en passant and castling are not legal moves. The input will be a position with White to move. The position will be one that may arise from the starting position of chess via a series of moves legal in the modified rule set. White will have at least one legal move available. Your program must determine whether, starting from the input position, there exists any sequence of legal moves that ends in Black checkmating White's king.

Either a program utilizing standard input and output, or a function accepting a string and returning a number is acceptable.

Input will be given in FEN notation, but excluding the last 4 tokens – only the locations of the pieces on the board are described.

The output shall consist of 1 if checkmate is possible, or 0 if it is not.

Restrictions

  • You may not use external libraries.
  • Your source code must fit inside a post on this site.
  • The program must halt in under 1 minute.

The winner is the first competitor to submit a correct program. A program shall be considered correct if no one provides an input that causes the program to fail to produce correct output in time for three days after the program is posted.

Examples

Input

kb6/8/8/8/8/8/8/KB6

Output

1

Input

1kb5/8/8/8/8/8/8/KB6

Output

0

Input

3k4/8/1p1p1p1p/pPpPpPpP/P1P1P1P1/8/8/3K4

Output

0

---------------------------

Feedback

Suggestions for improvement are welcome. I would most like to have some input on the victory condition. Is it too difficult to achieve? Should I score it on a fixed set of positions instead?

share
2  
The three day rule is a bad one. If an answer is incorrect, it's incorrect, and the possibility that no-one paid it much attention in the first 72 hours after posting shouldn't change that. –  Peter Taylor Sep 19 at 19:45

Play Wythoff's Nim Perfectly

Goal

Your goal is to write a perfect player for the game of Wythoff's Nim in as few bytes as possible. This player will take as input a position in the game and output the position resulting from its move. It must play perfectly, meaning that it must win every game theoretically possible.

Wythoff's Nim

Wythoff's Nim is a deterministic two-player game played with two piles of identical counters. Players alternate turns, and on a player's turn, he or she must do one of the following:

  1. Remove one or more counters from the first pile
  2. Remove one or more counters from the second pile
  3. Remove an equal number of counters (one or more), from both the first pile and the second pile.

Of course, piles can't be negative, so you can't remove more from a pile than it contains, though you can go to 0. Whichever player remove the last counter wins the game.

For the more geometrically-minded, here is an equivalent formulation of the game that you can play on this applet. A single queen starts on a cell of a quarter-infinite chessboard with a corner in the bottom-left. We can imagine labelling the cells of the chessboard with non-negative coordinates (x,y) so that the bottom-left corner is (0,0). Players alternate moving the queen, which moves like a chess queen, but restricted to three legal directions.

  1. Down
  2. Left
  3. Diagonally down and left

Whoever moves the queen to the corner wins.

Associating the queen's coordinates to the sizes of the respective piles, it's easy to see both games are the same.

Winning Strategy

(This section talks about some standard game theory ideas related to winning strategies for anyone unfamiliar with then.)

Since Wythoff's Nim is a finite and deterministic game, it has a notion of perfect play. A perfect player is a strategy that will defeat any player from a theoretically won position, meaning a position in which there exists a winning strategy. In other words, if there exists a strategy that guarantees a win from the current position, then a perfect player must always win from that position against any player.

One way to define a winning strategy is to compute the set of winning positions (also called cold positions). Moving to such a position gives a theoretical win for the player that moved to it. From every non-winning position, there exists a move to a winning position, but there's never a move from a winning position to a winning position.

The first of these winning positions for Wythoff's Nim are (0,0), (1,2), (2,1), (3,5), (5,3). See the Wikipedia article for an explanation of an algorithm to find a winning strategy for Wythoff's Nim, as well as a formula to generate won positions.

Code requirements

You must provide a named function that implements the winning strategy, with input and output as below. Fewest bytes wins.

Your code should take in the current position and outputs a winning move in the form of the position after that move. You can imagine two bots playing against each other by alternately calling their moves functions. If no winning move exists, i.e., the position is a theoretical loss, your program should indicate so and forfeit.

Input

A pair (i,j) of non-negative numbers representing pile sizes, each at most 30. This can be two numbers, a tuple, a list, or whatever container you prefer.

Output

The position after your move in the same format as the input. This must be a legal move to a winning position. If there's multiple such moves, any is fine.

If there's no winning move, you must indicate this in the output. Any output like False, None, 0, or (-1,-1) will do, as long as it's not a legal position, and is the same for every input with no winning move.

Your program must run within a reasonable amount of time. So, an exponential recursive game tree search will not suffice. If you want to precompute and hard-code a strategy, that's fine.

Example runs

f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0) 
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,4)
f(25,30) = (18,30) # Or (8,13)    
share

Hardware Random-Number Generator (posted)

share
1  
@BetaDecay: Because they have some chance to win a popularity contest but be ultimatively boring IMHO. For codegolf, the effect would be comparable to a language tailored to the context and could produce results like from my_hardware_API() import *; print bitsum(tons_of_data());. –  Wrzlprmft Sep 21 at 8:45

The World in the Future - Posted

share
1  
This is the vaguest popularity contest I've seen that I am in favor it. –  Sparr Sep 20 at 17:56
3  
I just know from experience that someone will write an answer which for any value of n outputs simply . –  Peter Taylor Sep 20 at 20:48
1  
Maybe specify the possible type of (realistic) maps. Like 'maps': Geographical, Political (nations and border), Ecological...? Are these all okay as maps? –  AndoDaan Sep 21 at 10:28
1  
\: I just finished writing my answer to this question... –  mrfishie Sep 21 at 11:47
1  
@BetaDecay Hmm.. I really liked the really open-ended question - it could lead to many interesting and creative responses.. Too bad it was closed. I dont see the problem with having 'too broad' popularity contests though, because, after all, they are popularity contests - the most creative responses are rewarded. –  mrfishie Sep 22 at 3:23

Edit: I'll have to clarify the optional features and there may be more. Essential I want to have the basic features covered, and if anything beyond gets implemented because it saves characters that is okay, but not required.

Edit: Updated but still working on it. Will definitely include edge cases and more examples as test cases.

Edit: It might be cool to have this implemented as a function, and then have some follow up questions where you are allowed to call the function created here while only counting the function call as characters, and not the contents.

Still working on the specifics, but getting it the idea out there.


2-Dimensional Regex

Given a 2-Dimensional regex and a block of text, do a match, a single search and replace or a global search and replace depending on the input.

Implement this as a function. The input should be two arguments to the function. The first is the regex, and the second argument is the string to match. The output should be a truthy or falsey value when doing a match, or the string when doing a search and replace.


Match

Input:

/aaa/
/bbb/
/ccc/

and

aaaab
dbbba
ecccc

Output:

A truthy value

Single Search and Replace

Replace the first instance of the match. The search order is the match that includes the top most character. If multiple matches end up with the top-most character on the same line, then include the left-most match.

Input:

s/bb/cc/
 /bb/cc/

and

abbaabba
bbbaabba
bbbaaaaa

Output:

accaabba
bccaabba
bbbaaaaa

Global Search and Replace

Replace all occurrences of the match. Matches do not overlap, and you use the same search order as the single search and replace.

Input:

s/bb/cc/
 /bb/cc/

and

abbaabba
bbbaabba
bbbaaaaa

Output:

accaacca
bccaacca
bbbaaaaa

Another example:

Input:

s/aba/bbb/
 /aba/aba/
 /aba/bbb/g

and

aaaabaaaa
  aabaababa
aababaababa
aabaaabbaba
 aba

Output:

aaabbbaaa
  aabaabbbb
aabbbbababa
aabaaabbbbb
 aba

Rules

  • Only ASCII characters 32 through 126 are valid.
  • Character classes are valid, [a-c4-6] would match an a,b, c, 4, 5, or 6. And [b?7] matches one b, one ?, or one 7.
  • . matches any character.
  • Use \ to escape there special characters to match their literal character instead of their special meaning: {}[]/\.?*.
  • a? matches 0 or 1 a's.
  • b+ matches 1 or more b's.
  • c* matches 0 or more c's.
  • b{2} matches 2 b's. Ranges such as {2,5} to match 2 to 5 b's is optional.
  • g flag replaces all of the occurrences, without it only the first occurrence would be replaced. This flag is optional.

Optional features:

  • Capture groups are optional. Please specify whether to use () or \(\) to match literal parenthesis.
  • Grouping such as (ab)+ matching all of abababab.
share

Coloring Book

Given a black-and-white raster line drawing (no anti-aliasing, with fully enclosed regions), write a program that will color it in. Something maybe like below, though I'd clean up messy JPGs into clean B&W PNGs to start with:

Could either be a , to give freedom in create more interesting output (gradients, patterns, how to select "better" colors, other images). Along the lines of patterns and gradients, I'd opt for simpler stock "prompts", preferably animals, to show off solutions:

...or perhaps if each region has a specified color given by a swatch inside it: so the program would basically need to find-the-color then flood-fill. Sounds boring, I prefer more creativity.

share
1  
If you can come up with a testable criterion, you might be able to get an interesting code-golf which asks for cel shading rather than just floodfill. –  Peter Taylor Oct 10 at 10:42

Balda AI in under 8192 bytes

Balda is a Russian word game which bears some similarities to Scrabble. Your task is to write an AI for an English version of it. However, because you can place any letters, the game would be easy if you knew all the words in the English language - hence, your entire program, including any word list, must be 8192 bytes or less.

The Game

The game consists of a square of 5x5 cells; each cell can be empty or hold one letter. At the start, a randomly selected 5-letter word is placed into the middle row. Example (please excuse my terrible ASCII art skills:

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
| P | L | A | N | E |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

There are two players. Each turn, a player must place one letter into an empty cell - any letter may be used. They must then compose a word which contains this letter. Words consist of horizontally and vertically adjacent letters; they can be backwards, upside-down, in a circle or any other shape. The player then receives one point per letter in this word. Words must be singular common nouns and at least 3 letters long. No word may be used twice in one game.

The game ends when there are no empty cells left, and the player with the most points wins.

Part of an example game:

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   | T | N |   |   | < TURN 1: Player 1 writes PLAN; Player 2 writes PLANT. Score 4:5
+---+---+---+---+---+
| P | L | A | N | E |
+---+---+---+---+---+
|   |   |   | T | T | < TURN 2: Player 1 writes PLANET; Player 2 writes TENT. 10:9
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Control, Input, Output

Your program will be invoked once per turn and at the end of the game, with the following arguments, where game_status is 0 if the game is still in progress, 1 if it ended because no spaces are left, 2 if it ended because player 1 failed to provide a word, 3 for player 2, 4 if player 1 gave an invalid word and 5 for player 2:

your_player_number player1_score player2_score game_status

The previously used words and the game board (separated by a line with a *) will be provided on standard input, in the following format (blank cells are underscores):

PLANET
PLANT
TENT
*
_____
_TN__
PLANE
___TT
_____

It has 30 seconds to output a move in the following format. In the example, the N of PLANT is in row 2 and column 3:

ROW_NUMBER COLUMN_NUMBER LETTER_PLACED WORD_LETTER1_ROW WORD_LETTER1_COLUMN WORD_LETTER2_ROW WORD_LETTER2_COLUMN ..........

Player 2's second move in the example would be written as follows. 4 5 3 5 3 4 4 4 are the co-ordinates of each of the word's letters, in order.

4 4 T 4 5 3 5 3 4 4 4

Rules

  • Your program must be 8192 bytes or shorter at the start of the tournament. However, it may create any files and keep them between tournament games - hence, it can learn from its opponents.
  • Your program must have a name and version numbering.
  • Please provide instructions on how to run your program on Windows 8.1.
  • Libraries which provide word lists or are designed for word puzzles are not allowed.
  • Libraries created after this challenge was posted are not allowed.
  • Standard loopholes are forbidden. No web access.
  • Existing compression algorithms such as gzip are allowed, and you may use libraries to decompress them, but the decompression must be done in your program.
  • You must write a complete program, not a function.
  • If the control program detects that no words can be written, the game ends and the player with the most points wins.
  • If words can be written, but a player cannot submit a valid word in 30 seconds, they lose regardless of their score.
  • This is the official word list.
  • This is the same list, but only with five-letter words (i.e. those that can be the starting word)
share
1  
@Geobits 1. I forgot that. I'll add that in. 2. That's a big loophole. I'll change it to "if you can't submit a valid word, but there is one possible, you lose" and "if no words are possible, the game ends normally" –  professorfish Oct 6 at 20:47

Orbital Mechanics [help wanted]

I need help specifying what input/output is required - if you have a suggestion for what the input/output format of the ephemeris should be, please post in the comments

How hard can Rocket Science be, anyway?

(Storyline taken from PhiNotPi's challenges linked below)

You are still the head programmer on the ill-fated U.S.S. StackExchange. You have guided it through the ASCII art solar system and the floating point cluster. Now, on another mission, the computer has crashed, and can't operate at full power. You need to make calculations of your orbit in order to plot a safe course. However, due to the limited free DEEEPRAROM* of the spaceship, you must write your program in as few characters as possible.

*Dynamically Executable Electronically Erasable Programmable Random Access Read Only Memory

Input

  • A description of your orbit at the moment of your burn, and what kind of orbit it is.
  • The gravitational field strength of your planet. Assume that it is spherical, and that no other effects change your orbit (gravitational perturbations of moons, atmospheric drag).
  • A direction that the burn will be carried out in
  • The delta-v of the burn

[More details coming soon]

Output

Your ephemeris after the burn is carried out, in the same format as the input. Assume that the burn is instant.

share
1  
Orbital elements? –  Peter Taylor Oct 21 at 15:36
1  
Can I submit my answer as a kerbal space program video? –  stokastic Oct 22 at 15:50

DTMF Decoder

(?)


Our spies have intercepted super-secret codes being sent to the enemy in some archaic code! Can YOU decode the captured signals and save the republic?

Find the audio clips at this GitHub repo or in this repo ZIP (7 MB).

Each audio file is 8 kHz and 16-bit, provided in both WAV format and text where each line is one sample. Each file contains 30 tones, each no shorter than 100 ms and with an inter-symbol gap also no shorter than 100 ms of "silence" (subject to noise). The testtones.wav file contains all digits, each 200 ms long, separated by 200 ms.

For reference, each of the symbols/tones/keys/digits is comprised of two superimposed sine waves:

DTMF Table

The difficulty increases as the files progress, with ever-increasing amounts of noise present. level01.wav is basically perfect (except for unavoidable quantization noise), level02.wav starts at a signal to noise ratio of 10, and level08.wav has a SNR of about 1 (equal parts signal/noise). The last file (level16.wav) has a signal to noise ratio of approximately 3%, pretty awful, but I think the theoretical limit is down at about 0.1%. That may be the case only if you know the symbol timing, however, and here the symbols are of variable length.

Your score is the highest level file you can decode without error, with additional tiebreaker points for tones successfully decoded from the next higher difficulty.


share
2  
Nice idea. If you want to make it code golf, I'd probably leave out all the fanciness and require 100% accuracy. If you want to include additional and varying amounts of noise and phase shifts, I think this should rather be a code challenge and you'd need to provide a large benchmark set of audio files to test against. –  Martin Büttner Oct 18 at 0:15

Deduce the Irreducibility of a Finite Field Polynomial

Given a polynomial whose coefficients are in a finite field, deduce whether or not it is irreducible, without using any built in polynomial handling / computer algebra.

Your program/function will take two inputs:

  • a prime number for the order of the Finite Field
  • some representation for the not-necessarily-monic polynomial

Output a truthy value if the polynomial is irreducible, and a falsy value otherwise.

Some test cases; your program must run in a reasonable time for this (ie 1 hour is definitely too long):

>>> F = 2, f(x) = x^3 + x^2 + x + 1
false
>>> F = 5, f(x) = x^4 + 4x^3 + 4x^2 + x
false
>>> F = 2, f(x) = x^4 + x + 1
true
>>> F = 5, f(x) = x^3 + x + 1
true
>>> F = 5, f(x) = x^6 + 2x^4 + 2x^3 + x^2 + 2x + 1
false
>>> F = 2, f(x) = x^6 + x^2 + 1
false
share
1  
Now that I almost have an answer to the polynomial factoring question I can say that the test cases can be handled by brute force in a slow language in a few seconds. It's the case over Z that allows tough performance requirements with simple test cases. –  Peter Taylor Oct 28 at 7:54

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

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

Given a text, determine the language it is written in. The possible languages are: English, Danish, Romanian and Hungarian. The shortest program wins.

Some examples of text in each language can be found at Project Gutenberg

You are required to include examples of runs on text files other than the ones provided here.

The input file name is given as a command line argument. Except the input text, you are not allowed read additional files (e.g. to train your program) so please encode any data in your program.

Your program must output on of the following words English, Danish, Romanian, Hungarian.

Examples

$ ./language pg2600.txt
English
$ ./langauge pg12167.txt
Danish
$ ./language 11756-0.txt
Romanian
$ ./language 30163-0.txt
Hungarian
share

Metagolf: Catlike Piet

The goal of this is to write a catlike program, which would be executed (in a Unix environment, though you needn't stick to that) by the following:

yourprogram < file > output
piet output

where piet output writes the contents of file to stdout. That is, you're to generate a Piet program which prints the input to yourprogram.

One-liners

Straight line programs can be written in Piet... in straight lines. If you're willing to take a hit to your score, your output can take the form of a string of commands:

=  none (continue color block)
|  push
^  pop
+  add
-  subtract
*  multiply
/  divide
%  mod
~  not
>  greater
.  pointer
\  switch
:  duplicate
@  roll
$  input number
?  input character
#  output number
!  output character

which is trivial to convert to a Piet program with the following (partially golfed) Python code:

def P(s):
 h=v=0;l=len(s)+1;R="P3 %i 2 255 192 0 0 "%(l+2)
 C=[1,3,2,6,4,5];V=[0,192,192,255,0,255]
 for x in map("=|^+-*/%~>.,:@$?#!".find,s):
  C=C[x//3:]+C[:x//3];V=V[x%3*2:]+V[:x%3*2]
  for i in [1,2,4]:R+="%i "%V[(C[0]//i)%2]
 return R+"255 "*4+"0 0 "+"255 "*l*3+"255 0 0 "*2

The dimension of said program is (n+3) x 2 if there are n characters in the string.

Scoring

Your code will be judged on the maximum dimension of the images that it outputs.

  • Part 1: Take the maximum score taken over all ascii codes (that is, single-character inputs), discounting EOF.

  • Part 2: Take the score for the input "Hello. My name is Inigo Montoya. You killed my father. Prepare to die."

Your score is the product of the scores in part 1 and part 2.

Punishment: Double your score if you write one-liners as above (that is, if you don't output an image).

Bonus: If your program is written in Piet, take the square root of your score above.

share

You must log in to answer this question.

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