457
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2559 Answers 2559

3
\$\begingroup\$

Originally posted on main site, moved here for more suggestions. Better scoring mechanics required.

Introduction

I've been browsing all those challenges and was thinking "yeah, they're good, but what if we make GoL one?", so here it goes.

Challenge

Build starting setting for either Conway's Game of Life or other similar cellular automaton (restricted to ones with binary cell state) which after known amount of generation will include square area containing representation of QR code decodable to string "Hello, world!".

  • Cell (non-empty state) is interpreted as black pixel, no cell as white.
  • Your automation should take at least one generation until result (no hardcoded results allowed).
  • Your automation operates on infinite board.
  • Not sure if this option will be useful, but you can specify scaling ratio: single integer, setting side of square encoding single pixel. Pixel's color is color of cell dominating by count in it (you can specify 50/50 edge case resolution in your answer). Obviously, in this case side of output area should be proportional to scaling ratio. This option doesn't affect scoring.
  • It's not necessary, but nice to provide either link to online demo or .rle file.

Example result

enter image description here

Decodes to "Hello, world!"

Scoring

Your score is calculated as

score = (initial amount of cells)^2*(number of generations until result) + (number of cells out of output area)*5

Lower score is better.

Happy GoLfing!

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this challenge is interesting, although I suggest that the scoring criterion be a combination of the number of initially on cells and the number of generations necessary to get to the final output, without counting the number of on cells in the output (otherwise there's an aspect of QR code golf in the challenge as well, which complicates matters more). Also, I don't really understand the 4th bullet point. Finally, you seem to want to allow different binary cellular automata to compete, just like different languages. Is this true? \$\endgroup\$ – Erik the Outgolfer Jul 14 at 22:48
  • \$\begingroup\$ @EriktheOutgolfer Why would including amount of cells out of output area be bad? It only counts cells which aren't part of QR code, so it seems acceptable. 4th point may probably need some illustrations to make it easier to get (or just remove that). You got the last part right. \$\endgroup\$ – val Jul 14 at 23:34
  • \$\begingroup\$ Oh, I misread the "out of output" part. So you allow extraneous on cells outside of the QR code with a penalty? \$\endgroup\$ – Erik the Outgolfer Jul 14 at 23:36
  • \$\begingroup\$ @EriktheOutgolfer I think that is more or less fine to have some cells on field as long as output in specified area is correct by itself. \$\endgroup\$ – val Jul 14 at 23:37
  • 2
    \$\begingroup\$ Could you clarify what classes of automata are eligible? You've specified only binary (two possible cell states). What neighbourhoods are valid? Only the standard 3 by 3 Moore neighbourhood, or also other size and shape neighbourhoods like Von Neumann neighbourhoods? Must all cells in the neighbourhood contribute equally to the outcome (a totalistic automaton) or can different patterns of the same number of "on" cells give different results? \$\endgroup\$ – trichoplax Jul 16 at 21:06
  • 1
    \$\begingroup\$ Where you choose to draw the line is entirely up to you, but it could have a large effect on the nature of the challenge. For example, if arbitrary size and shape neighbourhoods are allowed, with rulesets based on the arrangement of "on" cells rather than just how many are "on", it may be possible to choose a ruleset that gives the output in a single step (maybe - I haven't thought it through). Whether you see that as a bad thing or an interesting way of solving the challenge will determine how restrictive you choose to be. Personally I'd stop short of allowing quite that much flexibility... \$\endgroup\$ – trichoplax Jul 16 at 21:09
  • \$\begingroup\$ Is there a standard for QR that avoids all disagreement as to what's a valid code? On further thought, it might be better just to requre a fixed output pattern, like some pixel version of Heelo World, and not have the whole QR layer. \$\endgroup\$ – xnor Jul 16 at 21:35
  • \$\begingroup\$ In particular, following @xnor's comment, does "decodable to" mean that errors are allowed as long as they're below the threshold for correction? \$\endgroup\$ – Peter Taylor Jul 17 at 10:55
3
\$\begingroup\$

How long's left?

Posted here.

\$\endgroup\$
  • \$\begingroup\$ Shouldn't the third test case be FifTy Nine MiNutes And ForTy Six SeConds? \$\endgroup\$ – Erik the Outgolfer Jul 9 at 19:26
  • \$\begingroup\$ @EriktheOutgolfer Thanks, fixed \$\endgroup\$ – Geza Kerecsenyi Jul 9 at 19:27
  • \$\begingroup\$ @Shaggy the challenge here isn't to calculate the number of syllables: it's to find the first number that has the same number of syllables as the distance from the current time. \$\endgroup\$ – Geza Kerecsenyi Jul 11 at 21:14
  • \$\begingroup\$ Ah, OK, I get it now. Yeah, I think that's sufficiently different, so; ignore my previous comment! \$\endgroup\$ – Shaggy Jul 11 at 21:17
  • \$\begingroup\$ Could you please clarify how many syllable each number has? (A list should help.) \$\endgroup\$ – tsh Jul 12 at 7:38
  • \$\begingroup\$ @tsh done, see now. \$\endgroup\$ – Geza Kerecsenyi Jul 12 at 15:05
3
\$\begingroup\$

Irish Snap: Variant Rules

Introduction

Recently, me and a couple of my friends decided to play some cards, and one of them suggested the game 'Irish Snap', which was the inspiration for this challenge. However, I later learnt that the game has a lot of different rules that work ,some of which are listed here. The rules that are in this challenge aren't currently listed on that page, hence the name, 'Variant Rules'

The Challenge

Given an array of 3 cards, output a truthy or falsey value depending on if they make a valid snap in a game of Irish snap.

Input

The input will be an array of 3 numbers, ranging from 1-13 inclusive, with 11 being jack, 12 being queen and 13 being king. The last number in the array will be the number at the top of the stack of cards.

Rules

The 4 different criteria for if cards make an Irish snap are a snap:

  • The top and middle cards are the same
  • The top and middle cards have a difference of one
  • The top and bottom cards are the same
  • The top and bottom cards have a difference of one

If any of these criteria are met, you must output a truthy value. As well as this, for the two criteria that require the cards to have a difference of one, it 'wraps around', meaning that an ace and a king are considered to have a difference of one, and vice versa.

Test Cases

Input -> Output
1 13 7 -> False
1 4 13 -> True
9 3 6 -> False
8 9 7 -> True
2 6 5 -> True
12 5 11 -> True
10 4 8 -> False
12 13 7 -> False
9 7 10 -> True
7 3 1 -> False
\$\endgroup\$
  • 1
    \$\begingroup\$ Wikipedia describes a substantially different game under the same name. Is there any less ambiguous name for this? \$\endgroup\$ – Peter Taylor Aug 6 at 8:27
  • 1
    \$\begingroup\$ Although I don't think there is a less ambiguous name for it that I can find, the version I described is a combination of the alternate rules listed below the section you linked: 'conventional snap', 'runs', 'sandwiches' and the last rule I listed is basically a combination of 'runs' and 'sandwiches'. How could I change the name to reflect this? \$\endgroup\$ – EdgyNerd Aug 6 at 8:38
  • \$\begingroup\$ Should I change the name to "Ultimate Snap", as that's what Wikipedia says those rules are commonly referred to as? \$\endgroup\$ – EdgyNerd Aug 6 at 8:42
  • 1
    \$\begingroup\$ I think runs as described requires all three cards and in the right order. Maybe "Irish snap: variant rules" would be a suitable title, and the introduction can reference Wikipedia and say that the exact rules we'll be using aren't listed (at time of writing the question). \$\endgroup\$ – Peter Taylor Aug 6 at 8:49
  • \$\begingroup\$ Ok, I've added in all of those suggestions \$\endgroup\$ – EdgyNerd Aug 6 at 11:23
  • 1
    \$\begingroup\$ As our token Irishman, I endorse the keeping of "Irish Snap" in the challenge name! \$\endgroup\$ – Shaggy Aug 7 at 21:22
  • \$\begingroup\$ Do you think I'll be able to post this now? \$\endgroup\$ – EdgyNerd Aug 20 at 9:44
3
\$\begingroup\$

Find the Lowest Common Ancestor of Two Nodes In A Binary Tree

Any two separate nodes in a binary tree have a common ancestor, which is the root of a binary tree. The lowest common ancestor(LCA) is thus defined as the node that is furthest from the root and that is the ancestor of the two nodes.

The following are binary trees and the lowest common ancestors of the some of their nodes.

Binary Tree 1

The LCA of 13 and 15 is 14.

The LCA of 47 and 49 is 48.

The LCA of 4 and 45 is 40.

The LCA of 13 and 14 is 14.

Challenge

Write the shortest program possible that accepts as input the root of a binary tree and references to any two nodes in the binary tree. The program returns a reference to the LCA node of the two inputted nodes.

Restriction

The binary tree does not have nodes with parent field references in any form. You may not use parent field references in your program.

Input

The root of a binary tree and references to any two nodes in the binary tree. This may be in the form of a reference to the root object or even a list that is a valid representation of a binary tree.

Output

Returns a reference to the node that is the LCA of the two inputted nodes.

Definition of a Binary Tree

A tree is an object that contains a value and either two other trees or pointers to them.

The structure of the binary tree looks something like the following:

typedef struct T
{
   struct T *l;
   struct T *r;
   int v;
}T;

If using a list representation for a binary tree, it may look something like the following:

[root_value, left_node, right_node]
\$\endgroup\$
  • 2
    \$\begingroup\$ I mostly like your binary tree questions, but it would be nice if your definition was more inclusive of languages without the concept of pointers. Something like 'input will be a tree where a tree is either something containing a number and two other trees, or else something representing nothing. A tree must not be ambiguous'. This would include strings like [5[][7[6[][]][8[][]]], where a tree is [number tree tree] or [] as well as the usual standard binary tree structures and lists \$\endgroup\$ – Jo King Aug 9 at 6:45
3
\$\begingroup\$

Truth Table Composition

Given 2 or more truth tables, output the "shortest" way to compose the first N-1 tables to form the last (Nth) table.

Rules

  • Standard loopholes/io rules apply.
  • Input is a "list" of truth tables
    • A truth table is a "list" of rows that contain the inputs and the corresponding output
      • The input will always be the same length for a given table
      • There must be \$ 2^N \$ rows in a given table, where N is the number of inputs in the table
      • Each row must have distinct input
      • Inputs and outputs must both be "booleany" e.g.:
        • true/false
        • 1/0
        • truthy/falsey
        • "Bob"/"Sally"
    • The input can be in any reasonable format.
      • Any of the formats shown here are reasonable.
      • Taking the output first (ie for &: 1,1,1;0,0,1;0,1,0;0,0,0) is reasonable.
      • Input that requires non-trivial logic to convert is not reasonable.
      • When in doubt, ask in the comments.
  • Output is a "nested structure"
    • Each level of the nest contains information of the:
      • Truth table that was used
      • The ordered inputs (of this structure)
    • If a node is a leaf (one of the inputs to the final truth table) it must:
      • Be distinguishable from the other nodes
      • Contain the index of the input to the final table
    • Output format must be reasonable (see details under input)
  • "Shortest" is measured by the number of nodes in the output structure.
  • It will always be possible to construct the last table with the first N-1.
  • You do not need to handle invalid input.
  • This is , so the answer with the smallest asymptotic time complexity wins! Answers that do not aim to be efficient are also welcomed.

Yes, I'm done with rules now. Sorry.

Test Cases

For these test cases, the output is explained below. Note that this is not the output format you have to use! - $N is the Nnt input to the final table (0-indexed) - N(...) is the Nnt input table applied to ... (also 0-indexed) - Arguments are comma separated and are in this format. - Note that N() is different from $N; the former is the Nnt truth table applied to nothing (only valid in the case of truth tables 1 and 0), and the latter is the Nnt input to the final table.

Input:
(anything)

1 0 0
0 1 1
0 0 0
1 1 1

Output:
$1 (length 1; leaf; gives the second input)
Input:
1 0
0 1

1 1 1
0 0 1
0 1 0
1 0 0

1 0 1
1 1 0
0 0 1
0 1 0

Output:
0($1) (length 2; the first table (not) applied to the second input)
Input:
1 0
0 1

1

0

Output:
0(1()) (length 2; the first table (not) applied to the second table (true))
Input:
0 1
1 0

1

1 0
0 1

Output:
0($0) (length 2; the first table (not) applied to the first input to the final table)
Input:
0 1
1 0

1 1 1
0 1 0
1 0 0
0 0 0

1 1 1
0 1 1
1 0 1
0 0 0

1 1 0
0 1 1
1 0 1
0 0 0

Output:
1(2($0,$1),0(1($0,$1))) (length 8; "(A | B) & !(A & B)")

Meta

I think more test cases are needed, but am unsure what to add.

This is my firstsecond challenge, so all feedback is welcome!

\$\endgroup\$
  • \$\begingroup\$ The idea is good, I think. I had trouble understanding at first read though, and didn't understand at all your $ things. I suppose $1 is the same as 1() but I'm not sure. Suggested test case: Input : (1,0;0,1) ; (1) ; (1,0;0,1) with Output : 0() and not 0(1()) or 1(0()). \$\endgroup\$ – V. Courtois Aug 13 at 14:40
  • \$\begingroup\$ @V.Courtois $0 is the first input to the final table, $1, the second etc. 0(...) is the first input table, 1(...) is the second, etc. Any recommendations on a better format? \$\endgroup\$ – tjjfvi Aug 13 at 14:43
  • \$\begingroup\$ @V.Courtois Added your test case, though 0() is not a valid output as (1,0;0,1) takes in 1 input, not zero, it should be 0($0) \$\endgroup\$ – tjjfvi Aug 13 at 14:46
  • \$\begingroup\$ Do you mean $0 is the input on the first row of the output table? It got even more foggy... Plus, isn't a truth table's order meaningless? I mean, you even swapped the order of the rows in the last test case. And I just noticed now the # notation... Would you mind clarifying it all? Those signs are nowhere defined in the challenge ^^' \$\endgroup\$ – V. Courtois Aug 13 at 14:52
  • \$\begingroup\$ OH ; and by re-reading all the text I saw that your & is strange: why does 0&0 get 1?? \$\endgroup\$ – V. Courtois Aug 13 at 14:53
  • 1
    \$\begingroup\$ @V.Courtois The "&" is not an &, it is an iff/not xor \$\endgroup\$ – tjjfvi Aug 13 at 14:54
  • \$\begingroup\$ Oh my bad then, I didn't know for this one. \$\endgroup\$ – V. Courtois Aug 13 at 14:56
  • \$\begingroup\$ @V.Courtois Tomorrow I’ll revise the test case format \$\endgroup\$ – tjjfvi Aug 14 at 0:38
  • \$\begingroup\$ @V.Courtois I explained & slightly revised the notation; is it clearer now? If you have any suggestions, they would be very welcome. \$\endgroup\$ – tjjfvi Aug 14 at 12:30
  • \$\begingroup\$ Ah yeah, it looks clearer now. The test case of length 8 is really helpful in the process, too, for guys like me that in general read the test cases before reading what is the actual challenge about :) Let's hear other points of view about this challenge, for my part I don't see any problem now. \$\endgroup\$ – V. Courtois Aug 14 at 12:38
  • 1
    \$\begingroup\$ You can remove the "Exception: if there are 0 inputs, there must be 1 row." line, \$2^0=1\$. \$\endgroup\$ – Erik the Outgolfer Aug 15 at 22:16
  • \$\begingroup\$ For languages that support ND array, a ND array (each dimension has size 2) would be a natural representation of a N-ary truth table. \$\endgroup\$ – user202729 Aug 16 at 4:44
  • \$\begingroup\$ In your example is "1 1 1" = "(1, 1) -> 1" or "1 <- (1, 1)"? \$\endgroup\$ – user202729 Aug 16 at 4:46
  • \$\begingroup\$ Also: do you know any polynomial time solution to this problem? \$\endgroup\$ – user202729 Aug 16 at 4:48
  • \$\begingroup\$ @EriktheOutgolfer shame. I'll fix that. \$\endgroup\$ – tjjfvi Aug 16 at 13:16
3
\$\begingroup\$

Java vs C++

Note: I haven't invented this task, but haven't found it here and it seems fun. Feel free to tell me if it was done before. I'm changing it up slightly to try and fit the site more.

Story

In an unnamed company, some people use Java and some use C++. This was always a nuisance, and they kept on arguing which single language they should all be using. To settle the dispute, the management decided that they'll buy a translator program that will be able to rewrite their C++ programs to Java and vice versa. An important part of the translator will be a routine that will rewrite all the identifiers. This is because Java coders in the company write multiword identifiers in a different way than C++ coders in the company do. We will now describe both methods. In Java a multiword identifier is constructed in the following manner: the first word is written starting with a lowercase letter, and the following ones are written starting with an uppercase letter, no separators are used. All other letters are lowercase. Examples of Java identifiers are javaIdentifier, longAndMnemonicIdentifier, name and kSP.In C++ people use only lowercase letters in their identifiers. To separate words they use the underscore character '_'. Examples of C++ identifiers are cpp_identifier, long_and_mnemonic_identifier, name (here Java and C++ people agree), and k_s_p.

Task

Write the identifier translation routine/function/etc. Given an identifier, detect whether it is a Java identifier or C++ identifier (as defined below) and translate it to the other dialect. Translation must preserve the order of words and must only change the case of letters and/or add/remove underscores. You may assume all input to be valid, as checking was done for you in the superroutine.

More formally

A Java identifier only contains characters from [a-zA-Z] and starts with a lowercase letter. Every uppercase character is a word boundary.

A C++ identifier only contains characters from [a-z_] and additionally doesn't start or end with an underscores nor does it contain two adjacent underscores anywhere within. Every underscore is a word boundary.

Translation: switch every word boundary, that is, if it was an underscore, remove it and capitalize the following letter, if it was uppercase, prepend an underscore and lowercase the letter.

Input

The input consists of one line that contains an identifier. It consists of letters of the English alphabet and underscores. Other standard input styles are also valid.

Output

If the input identifier is a Java identifier, output/return its C++ version. If it is a C++ identifier, output/return its Java version. You may assume it will be at least one of those (both is possible).

Examples

long_boring_identifier  |  longBoringIdentifier
otherWay                |  other_way
same                    |  same
getHTTP                 |  get_h_t_t_p
invalid_Input           |  <undefined>

All the standard rules apply, none of the standard loopholes are allowed.

\$\endgroup\$
  • \$\begingroup\$ How vital is the validation to the challenge? \$\endgroup\$ – Unrelated String Aug 27 at 21:01
  • \$\begingroup\$ @UnrelatedString I think it's fairly integral if the story is considered. Gotta inform the user that they're feeding you crap. Also it should add an extra element of challenge. \$\endgroup\$ – Mr Redstoner Aug 27 at 21:07
  • 3
    \$\begingroup\$ @MrRedstoner Validation is generally considered tedious by the users of this site, rather than challenging. I'd recommend reconsidering - clearly the validation code could make use of the submissions as a subroutine. There are also a couple near dupes 1 2 but I haven't found a precise dupe. That said, thanks for using the sandbox! \$\endgroup\$ – FryAmTheEggman Aug 28 at 0:36
  • 1
    \$\begingroup\$ getHTTP would result in... get_h_t_t_p? get_http? Error? Some other thing? \$\endgroup\$ – Chas Brown Aug 28 at 1:42
  • \$\begingroup\$ @ChasBrown should be get_h_t_t_p, I shall add that. @FryAmTheEggman While I considered it part of the story, if those are the standards I figure I'll remove it and say the validation was done by a previous part of code. \$\endgroup\$ – Mr Redstoner Aug 28 at 5:24
  • \$\begingroup\$ "If it is neither, output/return a falsey value." I would change this to something like "If it is neither, any unspecified behavior is fine (return a falsey value; give an error; try to convert it somehow anyway; etc.)." As mentioned by @FryAmTheEggman, validation is usually considered a distraction of the actual challenge (and can sometimes even double the code of the program/function for those answering), so most challenges assume the given input will always be valid. Apart from that the entire challenge looks fine, so +1 from me. Thanks for using the Sandbox! :) \$\endgroup\$ – Kevin Cruijssen Aug 28 at 9:32
  • \$\begingroup\$ @KevinCruijssen Dang it missed that during the edit. Thanks for telling me! \$\endgroup\$ – Mr Redstoner Aug 28 at 10:42
  • \$\begingroup\$ What should be returned from an input of a__b (two underscores)? \$\endgroup\$ – Value Ink Aug 29 at 1:03
  • 1
    \$\begingroup\$ @ValueInk That would be invalid input. 'You may assume all input to be valid'. Therefore I refer you to the ANSI C standard for undefined behaviour. \$\endgroup\$ – Mr Redstoner Aug 29 at 6:00
3
\$\begingroup\$

Planting Steiner Trees

In the following we are talking about Steiner trees, which are similar to minimal spanning trees: The goal is connecting all nodes via some paths such that the resulting graph that is as short as possible. In contrast to minimal spanning trees when constructing steiner trees you can add additional nodes.

In the following we are talking about points in the real 2d plane and when we are talking about distances and lengths, we are talking about the euclidean distance.

Also, a graph will comprise a set of points where the edges are straight lines between pairs of those points. The length of a graph will be the sum of the length of all edges.

So a steiner tree is a shortest graph connecting all given points possibly with inserting additional points. The following image shows the difference between a minimall spanning tree (blue) and a steiner tree (red).

It is known that it is very difficult to find steiner trees.

enter image description here

Task

Write a program that accepts a list of 2d points and tries to find/approximate a steiner tree of minimal length connecting those points by possibly introducing more points. (It does not have to find the an actual steiner tree.)

The program should output a list of all the points (including coordinates) of the constructed graphs, a list of all edges (including their lengths), the total length of the graph and a graphical representation of the grap.

The program should have a running time of no more than about half a minute for each of the examples on a reasonable computer.

You should also explain how your algorithm works.

Scoring

The program must be evaluated on all the [NOT YET] given test cases. The score is the sum of the total length of all test cases. The lowest score wins.

Test cases

Square:
(0,0),(0,1),(1,1),(1,0)

Nonagon:
(cos(2*pi*a/9),sin(2*pi*a/9)) for a = 0,1,...,8

Ladder:
(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)

Meta: I need to find a good set of test cases. Suggestions are appreciated.

If you have any suggestions, feel free to edit/add. Any improvements of the text are appreciated too.

@El'endia Starman Pointed out some interesting n-gon configurations

\$\endgroup\$
  • 3
    \$\begingroup\$ It is known that Steiner trees for regular n-gons where 7 <= n <= 12 are simply the n-gon with one side removed. 4,5,6 all have interesting configurations though. \$\endgroup\$ – El'endia Starman Oct 31 '15 at 0:03
3
\$\begingroup\$

Shortest Persistent Object in 5-Char JS

The []+=` subset of JavaScript is known to be Turing-complete. A key part of the construction is obtaining persistent objects whose properties can be set and retrieved in a loop.

Most expressions won't evaluate to constant values. For example, [] != [] when compared by reference. However, some expressions, such as [].name, return the same object every time they are evaluated.

The Task

The following should hold when e is substituted with your submission:

  • (e) instanceof Object (this includes functions and arrays)
  • (e) == (e)

This is , so the shortest valid submission (measured in bytes) wins.

\$\endgroup\$
3
\$\begingroup\$

Cleaning the dishes

In this task, you will be given a bar of soap with a width of 1 or more units, which will be inputted as an integer. You will also be given a plate, which you will have to clean, using the soap as few times as you can. The plate will be inputted as a an array of 2 different characters, one of which is the 'dirty' character, and one of which is the 'clean' character. The plate will be at least 1 character. You will have to output an array with the 'clean' character representing the plate, and a third unique character to represent in what positions the bar of soap was placed. None of these 3 unique characters may be whitespace.

How much the soap cleans:

n//2-1 on each side for odd n
n//2-1 on the left side of the soap bar for even n
n//2   on the right side of the soap bar for even n

Input

An integer greater than or equal to 1. A series of 2 unique characters to represent clean portions and dirty portions. Here, '=' represents a dirty portion, and '-' represents a clean portion. '+' represents where the soap was placed.

IN : OUT

3 ===- : -+--
32 ================================ : ---------------+----------------
1 ==== : ++++
5 ----- : -----
4 -====- : --+---
3 -====- : --+-+-
7 === : +--
6 - : -
6 -==-===- : ---+----
5 -==--==- : ---+--+-
3 -==--==- : --+--+--

Rules

  • There are multiple solutions. Any one of them are acceptable, as long as they use the soap the minimum amount of times possible.
  • This is a contest, so the shortest answer in bytes wins!
  • The plate may only be non-whitespace characters, and have 2 unique characters.
  • The soap may only be one non-whitespace character, unique from the other 2 used in the plate.
  • Standard loopholes are not allowed.

Posted: Cleaning the dishes

\$\endgroup\$
  • \$\begingroup\$ If "soap input may only contain the characters '0' through '9', and may be multiple characters", then can it not be passed as an integer argument to a function? \$\endgroup\$ – Unrelated String Sep 4 at 4:15
  • 1
    \$\begingroup\$ i already specified rules about soap input in the first paragraph, so i will erase that rule. \$\endgroup\$ – girobuz Sep 4 at 20:34
  • \$\begingroup\$ There seem to be multiple possible outputs, e.,g.: 3 =-=-= could be either +--+- or -+--+, yes? If that is true, can we output any of them? \$\endgroup\$ – Chas Brown Sep 7 at 23:34
  • \$\begingroup\$ Yes, any output is acceptable, as long as it works, and is the minimum. \$\endgroup\$ – girobuz Sep 7 at 23:53
3
\$\begingroup\$

Battleship KotH

This is a pretty rough idea to start but I figured I would drop it in the sandbox so that people can start to think about it and I will remember to do it.

The idea here is a that combines the game, battleship with .

The rough idea is that two enemies would face off, each turn irradiating a location in their opponents source code. Then the opponents source code would be recompiled and then try and attack back.

Some additional thoughts I've had:

  • We will likely want to limit the size of the board to a specific rectangular size

  • I would like there to be a feedback from shooting your opponent (in the game battleship this is hit/miss) so that you are doing more than just firing randomly. Perhaps programs might irradiate a single bit (flipping its value) and get back its value before it was irradiated.

Language choice is a bit tough since I would like something multipurpose and flexible but I don't want to have to deal with the security issues that are involved in compiling and running a fully featured programming language.

\$\endgroup\$
  • \$\begingroup\$ radiation-hardening tends to work best with deletion. This is going to need a maximum byte count to be fair, otherwise the best strategy is excessive amounts of whitespace and comments. Love the idea though. \$\endgroup\$ – Beefster Sep 17 at 14:22
  • \$\begingroup\$ You don't actually have to limit yourself to a specific language on this one. It wouldn't be that hard to use a shell script to run whatever languages are available. One question though: is each program able to read the source code of the other or is each attack supposed to be blind? If you're worried about security, you could run the controller in a docker container or VM. \$\endgroup\$ – Beefster Sep 17 at 14:26
3
\$\begingroup\$

Injection from two strings to one string

\$\endgroup\$
  • \$\begingroup\$ Do you think that a reasonably number of languages won't implement the following: convert the strings into numbers (e.g. treat each character as a base 128 digit) then give a resulting string of those two numbers joined by some other character? I haven't spent too long thinking about it but that seems very short in most languages. I suppose there are other variants though where you map characters to some subset and then join them. \$\endgroup\$ – FryAmTheEggman Sep 24 at 20:42
  • 2
    \$\begingroup\$ @FryAmTheEggman I imagine the solution used is going to depend on the language: what builtins it has, if it's more high-level or low-level, etc. But there may well end up being a prevalent algorithm. \$\endgroup\$ – negative seven Sep 24 at 20:57
  • \$\begingroup\$ Why strings? Lists of integers, (even restricted to a range) work as well but don't have the complexities that strings do when it comes to printables etc. I feel like the simpler challenge is going to be the better one. \$\endgroup\$ – Sriotchilism O'Zaic Sep 26 at 3:30
  • 1
    \$\begingroup\$ @FryAmTheEggman Don't worry, I've thought of a totally different approach that I think would be shorter for many languages. \$\endgroup\$ – xnor Sep 26 at 4:46
  • 2
    \$\begingroup\$ @SriotchilismO'Zaic Restricting the character set seems to me like a reasonably simple detail, while making it about strings encourages creativity with string operations, converting to string representations, etc. Also, I personally think string input/output is much more appealing to look at and easier to consume than a list of numbers. \$\endgroup\$ – negative seven Sep 26 at 14:38
3
\$\begingroup\$

Golf Lathe Machine

You probably know what a Turing Machine is but do you know what is a Turning Machine (lathe)? Ok you already know.. and what about a Golf Turning Machine ??

Ok I tell you..

A Golf Turning Machine is a full program or function taking a list/array (or any convenient method) representing the Profile (P) of a turned piece and producing an ascii turned shape.

An ascii turned shape has square rotated by 45° cutting section instead of a circle so that we only need '/' and '\' characters to draw it. And it has '_' characters for the profiles: upper, lower and median.(like the one of this challenge : https://codegolf.meta.stackexchange.com/a/18149/84844 ) for simple and nice drawing purpose.

      _________
     /\        \
    /  \________\
    \  /        /
     \/________/

A Profile P is a container of positive integers values in the range 0 <= value < 26(minimum)
- Every value represents the radius of a 1 long character section, so the length of the container is the length of the piece obtained.
- P.S if you plan to use a string i will accept only letters as values, starting from 'a' or 'A' as 0 , you can also have lowercase and uppercase togheter but you cannot jump letters (for example "BaABcDCb" is acceptable as long as 'a' and 'A' represent the same value).
- 0 values at the beginning and at the end can not be considered.

Test cases:

[2,2,2,2,2,4,4,4,4,4,6,6,6,6,6,4,4,4,4,4,2,2,2,2,2]
             _____  
            /\    \ 
        ___/_ \    \__ 
       /\    \ \    \ \ 
   ___/_ \    \ \    \ \__ 
  /\    \ \    \ \    \ \ \ 
 /  \____\ \____\ \____\_\_\ 
 \  /    / /    / /    / / / 
  \/____/ /    / /    / /_/ 
      \  /    / /    / / 
       \/____/ /    /_/ 
           \  /    / 
            \/____/ 

.

[1,0,0,0,0,0,0,3,3,0,0,1] or   
[0,0,0,0,0,1,0,0,0,0,0,0,3,3,1,1,1,0,0,0]
         __
        /\ \   
  _    /  \ \_    
 /\\  /    \ \\       
 \//  \    / //              
       \  / /        
        \/_/        

.

[2,1,1,1,1,10,10,8,8,8,8,8,8,10,10,1,1,1,1,2]           

           __      __
          /\ \    /\ \
         /  \ \__/_ \ \
        /    \ \   \ \ \
       /      \ \   \ \ \
      /        \ \   \ \ \
     /          \ \   \ \ \
    /            \ \   \ \ \
   /  _           \ \   \ \ \
  /  /\\___        \ \   \ \ \
 /  /  \\__\        \_\___\ \_\
 \  \  //__/        / /   / / /   
  \  \//           / /   / / /  
   \              / /   / / /  
    \            / /   / / /  
     \          / /   / / /  
      \        / /   / / /  
       \      / /   / / /  
        \    / /___/ / /  
         \  / /  \  / /  
          \/_/    \/_/  

Rules :
- Margins are not specified.
- Standard loopholes are forbidden.
- Standard input/output methods.
- Shortest answer in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Does anyone have some test cases to suggest? Is it clear enough? \$\endgroup\$ – AZTECCO Oct 4 at 17:07
3
\$\begingroup\$

Code Golf Measurer © 2019

Hexdumps used with xxd look something like this:

00000000: 666f 6f20 6261 7220 7370 616d 2065 6767  foo bar spam egg
00000010: 730a                                     s.

Your task is to convert a hexdump in this form in to the number of bytes used.

Rules:

  • Usual loopholes forbidden.
  • This is , so shortest valid answer in bytes wins.
  • You may or may not include the newline at the end of text (0a). This means that if the hexdump ends in a newline (0a), that input may have it's output reduced by one.
  • An empty input must output 0.

Test cases:

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 2120 4865  Hello, world! He
00000010: 6c6c 6f2c 2077 6f72 6c64 210a            llo, world!.

returns 27 or 26

00000000: 0a                                       .

returns 1 or 0

00000000: 6368 616c 6c65 6e67 650a                 challenge.

returns 10 or 9

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 21         Hello, world!

returns 13


returns 0

Sandbox:

  • Is this clear?
  • Is this a duplicate?
  • Other tags?
\$\endgroup\$
  • 1
    \$\begingroup\$ Does the extra rule mean that the input can have an optional trailing newline, or that the results in all of your test cases could be reduced by 1? If you mean the former I recommend adding a test case that doesn't end with a newline. If you mean the latter then I recommend explicitly saying the file will end with a newline character. Also I suppose this is a string challenge. Thanks again for using the sandbox :) \$\endgroup\$ – FryAmTheEggman Oct 3 at 20:55
  • \$\begingroup\$ @FryAmTheEggman It means that all test cases could be reduced by one. This was intended as a code golf byte counter, and the newline most certainly isn't usually included. I'll clarify this and add another test case to highlight it. \$\endgroup\$ – gadzooks02 Oct 4 at 15:17
  • \$\begingroup\$ So: discard all the input except the last line, and parse hex? Or just output the last line and claim that your output is in hex? IMO it would be a more interesting problem with xxd input, where the last line is not present. \$\endgroup\$ – Peter Taylor Oct 5 at 9:00
  • \$\begingroup\$ @PeterTaylor If I were to switch to xxd, would that be a valid edit, or would that be too big a change such that I would have to post another challenge? \$\endgroup\$ – gadzooks02 Oct 5 at 9:45
  • \$\begingroup\$ I'm sure far more significant edits have been made to sandboxed challenges in the past. \$\endgroup\$ – Peter Taylor Oct 5 at 13:10
  • \$\begingroup\$ @PeterTaylor In that case, edited. \$\endgroup\$ – gadzooks02 Oct 5 at 14:52
2
\$\begingroup\$

Count Syllables

The goal of this challenge is to write a program that can count the syllables in a word as accurately as possible.

Input

On STDIN, your program will receive a number X followed by X lines, each containing a single word. Simple enough. (Should there be a limit on the size of X?) The words will come from this list.

4
challenge
to
count
syllables

Output

Your output should be to STDOUT and have X lines. On each line should be the number of syllables counted in that word.

2
1
1
3

Scoring

To score you program, it will receive a long secret list of words to test. All programs will receive the same list of words. For each word, the number of syllables that your program got wrong will be added to the score of the program. If it output a 4 or a 2 when the word had 3 syllables, then one point will be added. If it said a 15 instead of a 3, then 12 points will be added to the score. The lower the score, the better.

For example, if for the above input your program output 3 2 2 2 (which would be produced by a program that counts strings of vowels), then the program would receive a score of 2.

Rules

Your program should not access any external files (such as the word list). Also, your program should be no more than 5,000 bytes long (is this a reasonable limit?).

The winner will be the person whose program has the lowest score, therefor the most accurate syllable counter. The deadline for submissions is [some time at least a month away].

Suggestions

I am open to all constructive criticism. Is 5,000 bytes a reasonable limit for the program size? How long should the official scoring test be? How long should the deadline be?

\$\endgroup\$
  • 9
    \$\begingroup\$ This has one major flaw: the output is subjective. How many syllables do these words have? Every; victory; hierarchy; desire; oil; hour; poem. The only real way I see to work around this is for you to produce a marked-up version of the word list. \$\endgroup\$ – Peter Taylor May 29 '12 at 20:40
  • \$\begingroup\$ I was really worried about that, and I don't see a way around it. \$\endgroup\$ – PhiNotPi May 29 '12 at 20:42
  • 1
    \$\begingroup\$ I personally would love to see more language processing challenges. I agree with @PeterTaylor on the difficulty of some words. Perhaps taking a specific text(s) and identifying explicitly in the challenge which words will have how many syllables? \$\endgroup\$ – Gaffi Jun 8 '12 at 3:34
  • 2
    \$\begingroup\$ @PeterTaylor ...Or maybe you could filter ambiguous words out of the reference list? \$\endgroup\$ – user16991 Feb 8 '15 at 1:19
  • 1
    \$\begingroup\$ What's the point of the first line of input? \$\endgroup\$ – msh210 Apr 27 '16 at 20:05
  • 2
    \$\begingroup\$ If you provide a reference list, A hyphenated reference list, and hide a secret list which may or may not include members of the reference list, this would be a reasonable challenge \$\endgroup\$ – Rohan Jhunjhunwala Sep 17 '16 at 0:05
  • \$\begingroup\$ Do you plan to post this? If not, I'd be happy to adopt it. (If you don't respond within two weeks, by community standards, I'm allowed to do so.) \$\endgroup\$ – MD XF Aug 18 '17 at 3:20
  • \$\begingroup\$ The example of inaccurate program that would score 2 - did you mean to output 3 1 1 2 rather than 3 2 2 2? \$\endgroup\$ – Heimdall Nov 9 '17 at 18:31
  • \$\begingroup\$ A reference list could be dynamic: potential contestants can ask for words of their choice to be added to the list. They won't know what's on the secret list but will try to make their programs as accurate as possible (according to your syllable count) so they should always be able to ask for specific words they are not sure about. Of course, you could make it in different language. In my language, Slovene, it's much clearer how many syllables words have. How about Solresol, haha! \$\endgroup\$ – Heimdall Nov 9 '17 at 18:38
  • \$\begingroup\$ I am going to adopt this if you don''t respond \$\endgroup\$ – Christopher Dec 20 '17 at 16:48
2
\$\begingroup\$

Play Simple 2-Dimensional Minecraft

Recently I found this video of "HansLemurson" showing a computer that was built in minecraft, which runs minecraft. He is playing minecraft on a computer that was built in minecraft that is running on his computer. To be specific, it is a two dimensional version with an 8x8 grid of cells. There is gravity, block placement, and even jumping. It is worth noting that the computer is single purpose. The same person has built programmable computers, but making them single purpose allows the computer to be much smaller.

Details

The minecraft world is an 8x8 grid (one horizontal and one vertical dimension). The grid is comprised of either Xs (representing blocks) or empty spaces. The player is an X that is blinking on and off about once every second.

There are two modes in the game, controlled by a toggle switch. The first mode is movement. This is controlled by a WASD-like button arrangement. If the player chooses to move left/right/down, the computer checks to see if the space immediately in that direction is empty. If so, then the player moves into that space.

If the player chooses to move up, then the computer checks that the block underneath the player is solid. If so, then the player moves upward two units. Notice that this can propel the player into a solid block. If this happens, the player is obscured by the solid block, but can still move to an empty block next to him. When the player is inside on a solid block, the game continues as if the block isn't there, although the block is still there once the player leaves it.

After each move, the player falls down one unit if there is empty space there. This simulates gravity. This is also why moving up moves up two units, so that the gravity makes a net movement of up one unit. Gravity does not cause the player to fall all of the way to the ground, just one unit.

The second mode is block placement. In this mode, the same exact WASD buttons are used. Instead of moving the player, they toggle the state of the block in that direction. If the player presses "left" and there is a block there, then the block is destroyed. If there is not a block there, then a block is placed. Again after this move, the player is again subject to gravity. The blocks are not subject to falling.

Toggling the toggle switch does not count as a move, and does not invoke gravity.

The game board is a torus, so all actions (movement, block creation) can wrap around the board. The board does not scroll with the player. The player moves, and the blocks stay in the same place.

The challenge

You challenge is to write the shortest program that simulates this game. Your program should display and update the map correctly (with Xs as blocks, and with the blinking player). It should accept input from a button that toggles the state and four buttons for movement and actions. This is code golf.

There are imaginary bonus points for adding more features (block types, game size, etc) to your game.

Suggestions?

\$\endgroup\$
  • 2
    \$\begingroup\$ With more complicated challenges I find that it helps to do a reference implementation so that you have a very concrete idea of how much work is involved. Aside from that, I like it. \$\endgroup\$ – dmckee Jun 3 '12 at 20:11
  • \$\begingroup\$ Is the blink rate selected to fit with the ANSI escape sequence? Either way I would explicitly allow that, because it's the obvious way to do it on compatible terminals. \$\endgroup\$ – Peter Taylor Jun 5 '12 at 7:14
  • \$\begingroup\$ The blink rate wasn't selected to be anything specific. I think that I will broaden the restriction. Maybe any blink rate between 3 blinks per second to 1 blink every 2 seconds. \$\endgroup\$ – PhiNotPi Jun 5 '12 at 20:21
  • \$\begingroup\$ @programmer5000 No, for two main reasons: First, challenges can go extended periods of time in the sandbox before they are posted and/or adopted. In the past I've posted challenges after not touching them for 4 years. Second, deleting this answer will not reduce lag, as deleted answers are still present, simply not visible. Users with sufficient rep will see all 4040 answers in the sandbox, and you will too once you earn the "view deleted answers" privilege. \$\endgroup\$ – PhiNotPi Apr 13 '17 at 18:15
2
\$\begingroup\$

I've Got The Key, I've Got The Secret

A cryptography challenge in 2 parts.

Part 1

Implement a pair of programs in any language (the two programs could be in different languages if you wanted) to encode and decode a string of plaintext.

Input and Output

The encoder must take the plaintext (and an optional key) and return an encoded string. The decoder must take the cyphertext (and an optional key) and return the plaintext exactly as it was given to the encoder.

Restrictions

  • The encoding and decoding code must be entirely implemented in the language - no libraries or cryptography functions may be used.
  • The code (encoder+decoder) cannot be longer than 1024 characters.

Part 2

Implement programs (multiple programs per answer, one answer per entrant) which crack your opponents encryption algorithms.

Input

The cyphertext.

Output

The plaintext that generated the ciphertext.

Scoring

I will upvote all answers to part 1 which have working encryption and have obviously made an attempt at golfing their answer.

In order to be eligible to win, an entrant will have to have taken part in both parts of the question. Overall score will be (length of shortest program that cracks your code-(length of encoder+length of decoder)). Highest score wins and winning entrant's entries will be accepted on both questions.

\$\endgroup\$
  • 1
    \$\begingroup\$ The obvious place for this to fall flat on its face is if someone is able to implement AES or something similar within the 1024 character restriction. \$\endgroup\$ – Gareth Jun 13 '12 at 13:06
  • 1
    \$\begingroup\$ Probably better if the methods of the part one programs are disclosed in non-obfuscated language, though with the short length restriction this may not be necessary. \$\endgroup\$ – dmckee Jun 13 '12 at 15:23
  • 1
    \$\begingroup\$ Forget AES: RSA is easily doable. That aside, you need to define "crack" in part 2. \$\endgroup\$ – Peter Taylor Jun 13 '12 at 15:35
  • 1
    \$\begingroup\$ Also, it's not clear whether "optional key" means that it's optional to make the algorithm unkeyed (doesn't make much sense, I admit) or optional to supply it, in which case it uses a default key. \$\endgroup\$ – Peter Taylor Jun 13 '12 at 15:42
  • 1
    \$\begingroup\$ @PeterTaylor I just put optional in to leave it up to the implementer whether or not they wanted to have the key input or hard-coded (or use no key). I'd have thought everyone would have the key input into their program, but I didn't want anyone to feel forced into it by the spec. Hmm, if RSA is doable within the character restriction I'll end up with a load of unbreakable codes which would make for a pretty crap part 2. By crack I meant cyphertext goes in, some time later plaintext comes out. Would restricting the character count further help, or is this question beyond help? \$\endgroup\$ – Gareth Jun 13 '12 at 16:05
  • 2
    \$\begingroup\$ On that definition of crack, I can brute force for the length of the decoder plus a few bytes to iterate over all keys of the right length and some heuristics to check plausibility of the plaintext. The brute force cracker might even be shorter than the decoder if the decoder wasn't written in GolfScript... I think this question may be beyond help. \$\endgroup\$ – Peter Taylor Jun 13 '12 at 16:28
  • 3
    \$\begingroup\$ @PeterTaylor Okay, thanks. I like the 'build your own - knock everyone else's down' aspect of this question though. I'll have to find another area where it could apply. \$\endgroup\$ – Gareth Jun 13 '12 at 16:34
  • 2
    \$\begingroup\$ @Gareth I too like the competitive nature of this idea. I'm looking forward to a question with this plan in mind! \$\endgroup\$ – Gaffi Jun 13 '12 at 19:31
  • 1
    \$\begingroup\$ I think it would be better to split this into a "cops" post and a "robbers" post. \$\endgroup\$ – wizzwizz4 Feb 16 '17 at 9:46
  • 1
    \$\begingroup\$ @wizzwizz4 Wow, this is another blast from the past. I think this pre-dates the cops-and-robbers tag. I always seem to be ahead of my time. :-) \$\endgroup\$ – Gareth Feb 16 '17 at 9:49
  • 1
    \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 5 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:35
2
\$\begingroup\$

Countability of Sets of Finite Sets

The aim of this challenge is to code-golf a program which returns an iterator that will iterate over all possible non-empty finite sets of positive integers.

So if running long enough, this iterator should eventually touch on {1}, {2, 5}, {3, 6, 112} (ie none of these should occur "at infinity")

You may choose the order in which you iterate over these sets, but the order must satisfy the following requirement:

Under a particular ordering, if S is the i'th set to be returned by the iterator, then we shall call i the index of set S.

Let a restriction (k,T) be an assertion about a set S that says S has size k and T is a subset of S.

For a given restriction (k,T) and iterator IT, let the restricted iterator be the iterator which takes sets returned by IT and filters out sets that don't satisfy the assertion, iterating only over the ones that do. In other words, if IT iterates over the sequence of all sets, the restricted iterator iterates over the subsequence satisfying (k,T). Now if S is the n'th set returned by the restricted iterator, then we'll call n the restricted index of S with respect to (k,T)

Your ordering must satisfy the property that for any restriction there exists a polynomial P(x) such that for any set satisfying the restriction (with index i and restricted index n), i < P(n)

Note that the following ordering is not acceptable:

{1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} {4} {1, 4} {2, 4}...

This is the sequence that comes from counting 1, 2, 3, 4, 5, 6... and listing the set bits in the binary representation of each number.

This is because the restriction (1, {}) satisfies only the sets {1}, {2}, {3}, {4}... whose index i as a function of their restricted index is i=2^(n-1) which is not bounded by any polynomial


Sandbox Questions

The reason for the strange requirement at the end is to disqualify any variants on the most natural ordering which simply counts upwards from 1 and enumerates the set bits in each number. In this ordering, the n'th set of length-one occurs at index 2^n which is non-polynomial.

I posted this problem originally, but didn't think of the obvious solution and so I left out the final restriction. I'd like to re-post it with the extra restriction. But first I'd like to know what people think. Is there a better way I can word that restriction or a more natural restriction I could impose instead?

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't understand the extra restriction, so I can't suggest a rewording, but I can say that it needs one. (In particular: what is k? And what function does T serve? Is it really a parameter of the property?) \$\endgroup\$ – Peter Taylor Jun 18 '12 at 8:25
  • 1
    \$\begingroup\$ I don't understand it either. Maybe a sample of an ordering, satisfying the requirement, and another one, violating it, would help. \$\endgroup\$ – user unknown Jun 18 '12 at 15:31
  • 1
    \$\begingroup\$ I understand the restriction now, although I haven't worked through the full implications. Does allowing T to be non-empty make a significant difference at all? \$\endgroup\$ – Peter Taylor Jun 19 '12 at 6:52
  • 1
    \$\begingroup\$ I don't know. It may not. I guess the size part is the important part. I was just thinking that the ordering should be such that you run into all kinds of sets frequently. \$\endgroup\$ – dspyz Jun 20 '12 at 7:17
  • 1
    \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 5 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:36
2
\$\begingroup\$

Bad Voice Recognition Calculator

Overview:

Let's say you've decided to operate your computer using voice recognition software, but unfortunately you did a horrible job researching the various products out there and chose a package that does not recognize numbers as numerals, only words. (i.e. "one" (spoken) == "one" (typed), not "1".) Rather than spend more money to get another option, you decide to make do. Now you want to use the computer's calculator, but this poses a problem, since your machine doesn't know how to add "one plus one".

Objective:

Implement a basic calculator that will read in a string of the written-out equation, perform the correct calculations, then return the result in its text form. Your code should be as short as possible; this is code golf.

Rules/Constraints:

  • Input/output will be using your preferred method (STDIN, ARGV, etc.).
  • Your calculator must be able to handle input and output within the billions (non-inclusive) -1,000,000,000 < i < 1,000,000,000, but you may expand to more if you wish.
  • Decimal values and/or parts must be accepted (0 < i < 1) up to 3 places/digits.
    • When calculating answers, proper rounding must be used, so "three point one four one five nine two six" must be returned as "three point one four two".
  • Basic calculator functions required:
    • "Add"/"Plus"/"Sum"/"And" (+)
    • "Subtract"/"Minus"/"Remove" (-)
    • "Multiply"/"Times" (*)
    • "Divide"/"Divided"/"Divide by"/"Divided by" (/)
    • "Raise"/"Exponent"/"Power"/"To the power of" (^)
    • "<Base>Root"/"<Base>Radical" (√)
    • "Point"/"Decimal" (.)
    • "Pi" (π)
  • All strings in the list above must be accounted for in your code, capitalization does not matter.
  • Numbers may be presented as their full value ("one thousand") or by digit (one zero zero zero).
  • Negative numbers may be assigned using "Minus" or "Negative".
    • The string "Minus" bust be accounted for as an operator and identifier. (see example)
  • "And" is only acceptable as an operator, not as part of a named number.
    • "one hundred and one"
    • "one hundred one"
  • "a" or the absence of a number does not equate to any number; all numbers will be explicitly accounted for in the program input.
    • "a hundred" does not equate to "one hundred" and is not a valid input.
  • No more than 2 terms will be used.
    • "one plus one minus one" will not be implemented.
  • If an invalid input is supplied, your function/program should handle the error and exit gracefully with an error description.

Example I/O:

  • "one add one" --> "two"
  • "five thousand thirty four subtract ten thousand six hundred" --> "negative five thousand five hundred sixty six"
    • Alternatively: "five zero three four subtract one zero six zero zero"
  • "three root twenty seven" --> "three"
  • "ten minus minus ten" --> "twenty"
    • Alternatively: "ten subtract negative ten"

Sandbox Questions:

  1. Is this too basic/complicated? (I'm assuming some languages will handle this much more simply than the method I have in my head...)
  2. Does the title fit?
  3. Are there any constraints that should be added/lifted?
  4. Are any more examples needed for clarification?

Thanks for your input, guys!

\$\endgroup\$
  • \$\begingroup\$ Not everyone says numbers the same way. Does the parser have to treat the following as equivalent? "negative one hundred five", "minus one hundred five", "negative one hundred and five", "minus one hundred and five", "negative a hundred five", "negative a hundred and five", ...? \$\endgroup\$ – Peter Taylor Jun 15 '12 at 15:12
  • \$\begingroup\$ @PeterTaylor I had had a similar thought re: operators. ("plus" versus "add", etc.) I think it would be more interesting to account for all, but given the wide variety of possible inputs, it may generally be better to limit the options to a specifically defined set (which I have yet to define). \$\endgroup\$ – Gaffi Jun 15 '12 at 15:18
  • \$\begingroup\$ @PeterTaylor I've added some of these details. Please let me know if there's anything unclear about them. \$\endgroup\$ – Gaffi Jun 15 '12 at 16:10
  • \$\begingroup\$ I don't spot any ambiguities in the parser. There is still an ambiguity relating to decimals, though. What precision should be used? Also, I notice now that there's no winning condition. Is this intended to be code-golf? (Ugh - tons of strings which will have to be hard-coded in most languages. I expect Perl has a suitable parser already in CPAN, though...) \$\endgroup\$ – Peter Taylor Jun 19 '12 at 9:03
  • \$\begingroup\$ @PeterTaylor I don't know where I went... I've updated the spec. re: decimal places and objective. \$\endgroup\$ – Gaffi Jun 29 '12 at 13:24
  • 1
    \$\begingroup\$ @PeterTaylor metacpan.org/pod/Lingua::EN::Words2Nums \$\endgroup\$ – msh210 Apr 27 '16 at 20:37
  • \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 5 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:36
2
\$\begingroup\$

The One with Two Parts

The aim of this challenge is to create a pair of functions which scramble and unscramble any given piece of text.

Part 1

In part one you post your scrambling function, along with the length in characters and language of your unscrambling function (but NOT its code). The length of the scrambler does not affect your score so you needn't golf it unless you want to. The two functions may be written in different languages if you wish.

Input/Output

The scrambling function should take one argument only - a string containing the input text - and return a string containing the scrambled text. The unscrambling function should also take only one argument - the scrambled text - and return the original text. The input text will be limited to characters in the ASCII set range from 0 to 127.

Part 2

In part two you try to beat your opponents' scores for their unscrambling functions. You MUST use the language they specify for their unscrambler in part one. Please give just one answer to this question containing all your unscrambling functions making it clear which question in part one each function unscrambles (maybe each answer in part one should give its scrambler a name for identification?).

Once the closing date (TBA) has passed all participants should post their unscrambling functions in their answer to part one to prove the length, language and functionality of their function.

Scoring The participants score will be calculated as follows: (unscrambler length from part one) - (shortest unscrambler length from part two). The participant with the lowest score wins and will have their answers accepted on both parts of the challenge. To be eligible to win a participant must have taken part in both parts of the question.

Example

In part 1:

  • Bob posts a Python answer and says his unscrambler is a 165 character Python function.
  • Fred posts a GolfScript answer and says his unscrambler is a 59 character GolfScript function.
  • Joe posts a JavaScript answer and says his unscrambler is a 180 character PHP function.
  • Jim posts a Ruby answer and says his unscrambler is 163 character Ruby function.

In part 2:

  • Bob posts an 82 character GolfScript function to unscramble Fred's scrambled text. He also posts a 175 character PHP function to unscramble Joe's scrambled text.
  • Fred posts a 181 character PHP function to unscramble Joe's scrambled text.
  • Joe posts a 150 character Python function to unscramble Bob's scrambled text.
  • Jim posts a 156 character Python function to unscramble Bob's scrambled text. He also posts a 91 character GolfScript function to unscramble Fred's scrambled text.

The scores:

  • Bob scores 165 - 150 = 15
  • Fred scores 59 - 82 = -23
  • Joe scores 180 - 175 = 5
  • Jim scores 163 - 0 = 163

so Fred wins.

Miscellaneous

I suggest that the closing date be two weeks after the challenge begins, and that unscramblers be posted to part one within 48 hours of closing date in order to be eligible.

\$\endgroup\$
  • \$\begingroup\$ Are there any rules regarding scrambling? i.e. is "Stockholm"->"Stockhoml" a valid scramble? (it may not matter, but I'm curious. And to be clear, the scoring is the difference between your opponent's unscrambler length and your own for the same language? \$\endgroup\$ – Gaffi Jul 16 '12 at 16:39
  • \$\begingroup\$ @Gaffi No, you scramble however you want. If you want to just output the text as given that's ok, but you probably won't win with that strategy. The aim is to do it in a way that is easy for you to unscramble but difficult for all the others. That way your score will be smaller. Yes, the score is the difference between your score and the score of the best of your opponents' attempts. I'll add an example to make that bit clearer I think. \$\endgroup\$ – Gareth Jul 16 '12 at 21:27
  • \$\begingroup\$ I think this gives an advantage to people who use (relatively) obscure languages. If the scrambler is written in J and the descrambler in GolfScript then only people who know both can realistically attempt a descrambler. (NB the rules don't say how the score works if no-one attempts a particular unscrambler). \$\endgroup\$ – Peter Taylor Jul 17 '12 at 6:59
  • \$\begingroup\$ I did consider saying that programs that had no attempts at beating them were not eligible to win, but then I thought that if they were scored as though the shortest attempt to beat them was 0 then they wouldn't have much of an advantage. I'll add that into the example scoring. What do you think? I want to encourage answers that are clever or well obfuscated rather than written in Malbolge or something like that. \$\endgroup\$ – Gareth Jul 17 '12 at 7:28
  • 1
    \$\begingroup\$ Does it mean that since no one attempts to solve Jim's Ruby challenge his chances are minimal that he'll win? That would discourage complicated scramblers or difficult languages. \$\endgroup\$ – Howard Jul 17 '12 at 17:12
  • \$\begingroup\$ @Howard As it stands, yes that's how it would work. The alternative, as Peter Taylor points out, is that people using obscure languages have an advantage. I'm not sure how else I might score unscramblers that no-one has attempted to beat. Maybe give them a score of 0? Please, if you or anyone else has any suggestions for making the challenge as inclusive as possible, let me know. \$\endgroup\$ – Gareth Jul 17 '12 at 17:51
  • \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 5 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:37
2
\$\begingroup\$

Huffman Decoding

Write a programm which takes two strings as input and prints a text.


The first argument is a Huffman Tree, serialized in the following format:

  • every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
  • <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
      d e

where a would have the key 00, b 01, c 10, d 110 and e the key 111.


The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

  • the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
  • the bitstring is broken up into 6-bit chunks and mapped to this characters
  • if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
  • - : the last chunk was five bits long
  • = : the last chunk was four bits long
  • =- : the last chunk was three bits long
  • == : the last chunk was two bits long
  • ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-

Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

\$\endgroup\$
  • \$\begingroup\$ It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. \$\endgroup\$ – Peter Taylor Oct 8 '12 at 16:23
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:30
2
\$\begingroup\$

Compile BF to TM

Your task is to write a compiler accepting a Brainfuck program (previous challenge: Interpret Brainfuck, wikipedia: Brainfuck) as input and outputting a Turing Machine which produces identical output when supplied with the same (correct) input.

You may select the output format from among the various formats accepted by the answers to Turing Machine Simulator.

The following links may also be useful.
An introduction to programming in BF
BF is Turing-complete
Programming a Turing Machine
Programming Praxis: Turing Machine Simulator

Equivalently, you may write a Brainfuck interpreter in TM, or any partial compilation/interpretation which results in a TM program as described above.

If we consider squares of the TM tape to represent bits (blank=0, mark=1) of the BF memory, then eight squares represent a cell. Each BF instruction translates to a minimum of 8 states of the Turing Machine.

'>' "advance" (++ptr) could be implemented by eight states (sixteen transitions):

adv8 _ adv7 R _
adv8 1 adv7 R 1
adv7 _ adv6 R _
adv7 1 adv6 R 1
adv6 _ adv5 R _
adv6 1 adv5 R 1
adv5 _ adv4 R _
adv5 1 adv4 R 1
adv4 _ adv3 R _
adv4 1 adv3 R 1
adv3 _ adv2 R _
adv3 1 adv2 R 1
adv2 _ adv1 R _
adv2 1 adv1 R 1
adv1 _ link R _
adv1 1 link R 1

where 'link' represents the first state of the following instruction.

'<' "rewind" (--ptr) can be implemented similarly by making leftward movements and rewriting the same symbol just read.

'+' "increment" (++*ptr) can be implemented by a ripple-carry from the Least Significant Bit to the Most Significant Bit, borrowing "rewind" states to back-up to normal position. If the LSB is on the left, it would look something like this:

inc8 _ link N 1
inc8 1 inc7 R _
inc7 _ rew1 N 1
inc7 1 inc6 R _
inc6 _ rew2 N 1
inc6 1 inc5 R _
inc5 _ rew3 N 1
inc5 1 inc4 R _
inc4 _ rew4 N 1
inc4 1 inc3 R _
inc3 _ rew5 N 1
inc3 1 inc2 R _
inc2 _ rew6 N 1
inc2 1 inc1 R _
inc1 _ rew7 N 1
inc1 1 overflow N 1

where overflow is a HALT state.

For I/O, the simplest way I can think is to place all input on the tape after the memory area, and expand the alphabet to include a symbol indicating the dividing line between the memory portion and the input portion of the tape. In fact, by expanding the cell size to nine squares, this symbol can serve as an input pointer, advancing as the input is consumed. (So "advance" and "rewind" now need 9 states each.) And another new symbol is written in front of the current memory cell to serve as the memory pointer. Inputting a byte therefore consists of schleping each bit over the entire space between the two tape positions with something like this:

input _ set-memptr L _
input 1 set-memptr L 1
set-memptr _ find-inptr R *
find-inptr _ find-inptr R _
find-inptr 1 find-inptr R 1
find-inptr $ schlep-bit R $
schlep-bit _ schlep-blank L _
schlep-bit 1 schlep-one L 1
schlep-blank $ schlep-blank L $
schlep-blank _ schlep-blank L _
schlep-blank 1 schlep-blank L 1
schlep-blank * deposit-blank R *
schlep-one $ schlep-one L $
schlep-one _ schlep-one L _
schlep-one 1 schlep-one L 1
schlep-one * deposit-one R *
deposit-blank _ etc R _
deposit-blank 1 etc R _
deposit-one _ etc R 1
deposit-one 1 etc R 1

where "etc" represents going to get the next bit in similar fashion.

To perform a loop (all BF loops are "while" loops, so the exit control is at the beginning and the end has a simple goto back to the beginning), we need first to check is the current cell is zero,

zero8 _ zero7 R _
zero8 1 body R 1
zero7 _ zero6 R _
zero7 1 left1 L 1
zero6 _ zero5 R _
zero6 1 left2 L 1
zero5 _ zero4 R _
zero5 1 left3 L 1
zero4 _ zero3 R _
zero4 1 left4 L 1
zero3 _ zero2 R _
zero3 1 left5 L 1
zero2 _ zero1 R _
zero2 1 left6 L 1
zero1 _ exit-loop R _
zero1 1 left7 L 1
left7 _ left6 L _
left7 1 left6 L 1
left6 _ left5 L _
left6 1 left5 L 1
left5 _ left4 L _
left5 1 left4 L 1
left4 _ left3 L _
left4 1 left3 L 1
left4 _ left3 L _
left4 1 left3 L 1
left3 _ left2 L _
left3 1 left2 L 1
left2 _ left1 L _
left2 1 left1 L 1
left2 _ loop-body L _
left2 1 loop-body L 1
...
loop-body-final _ zero8 N _
loop-body-final 1 zero8 N 1

So assuming the machine starts at tape-location 0, and the input is on the tape starting at 0 and going to the right, the "startup code" for this arrangement would be

startup _ place$ L _
startup 1 place$ L 1
place$ _ left270000 L $
left270000 _ left269999 L _
...

Jeez! The output is going to be HUGE! It might be better to treat the BF memory as negative-indexed and reverse all the _L_s and _R_s in 'advance', 'rewind', 'increment', and 'decrement'.


Questions:

Bonuses for optimizations? If I can implement this myself and provide a complete example output, The bonus could be "subtract the difference between your program's output for the example input with the example output". So eliminating states would be far more valuable than shrinking the code. One could possibly achieve a negative score!


Edit: Actually I think this is unreasonable unless the Turing Machine is augmented with non-reading (movement-only or epsilon) transitions. Duplicating every letter of the alphabet just to move over one square is just ridiculously painful. That means this challenge won't link-up nicely with the other one. :(

What about, instead of implementing the compiler, just devise a translation scheme (as above) that leads to a smaller output for a trivial sample program (based on calculating, rather than coding)? "Back of the envelope" compiler.

\$\endgroup\$
  • \$\begingroup\$ "How much detail on BF do I need to supply? Can I simply reference the BF question?" A link to almost any site that describes the language will do. \$\endgroup\$ – dmckee Nov 5 '12 at 16:52
  • \$\begingroup\$ Winning condition? \$\endgroup\$ – Peter Taylor Nov 6 '12 at 13:43
  • \$\begingroup\$ "Longest prefix containing syntactically-correct Malbolge!" :) ... I'd say have none at all. Perhaps the questioner should be required to accept their own example answer? \$\endgroup\$ – luser droog Nov 6 '12 at 18:08
  • \$\begingroup\$ @PeterTaylor Apologies for my last comment. I thought we were on my other answer about the [fun] tag. . . . This one would be a golf: shortest code by character count. But I think a clever system of bonuses could make it interesting. \$\endgroup\$ – luser droog Nov 7 '12 at 10:06
  • \$\begingroup\$ The "Equivalently, you may write a Brainfuck interpreter in TM" option doesn't play very well with being a code golf - how are you going to count the length of the TM? \$\endgroup\$ – Peter Taylor Nov 7 '12 at 11:15
  • \$\begingroup\$ @PeterTaylor Since the TM question specified 5-tuples, I think it's sufficient to count the tuples (== transitions). You can reduce states by increasing the alphabet (or vice versa), but the transitions would remain constant, I think. \$\endgroup\$ – luser droog Nov 8 '12 at 5:25
  • \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 5 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:42
  • \$\begingroup\$ I'd like to adopt (work on and post) this challenge if you don't want to. Would I be able to? If you do not respond to this message within two weeks, by community guidelines, I am allowed to take it over. \$\endgroup\$ – MD XF Aug 18 '17 at 3:23
  • \$\begingroup\$ Yes, please. If you can do something with it, strike while the iron is hot. \$\endgroup\$ – luser droog Aug 18 '17 at 4:19
2
\$\begingroup\$

Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

Tree of Life after Kirtcher

Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

Eg. http://code.google.com/p/xpost/downloads/detail?name=ve6a.ps
//lotsoflines n = 1 ..12

Mandalas 1 - 12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

Draw the I-Ching Hexagrams in King Wen Sequence.

I suppose I need to implement this first to avoid copyright issues! :)

\$\endgroup\$
  • \$\begingroup\$ The I-Ching one would have to be in standard order to be remotely interesting, and then becomes as much about kolmogorov-complexity as graphical-output \$\endgroup\$ – Peter Taylor Nov 22 '12 at 21:24
  • \$\begingroup\$ For the others: images, please! \$\endgroup\$ – Peter Taylor Nov 22 '12 at 21:25
  • \$\begingroup\$ I've emailed the owner of the Alchemy pages asking for permission to use his copyrighted images. Awaiting response. \$\endgroup\$ – luser droog Jan 28 '13 at 8:25
  • \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 5 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:42
2
\$\begingroup\$

Polygon prefixes

Polygons are named after the number of sides that they have. A pentagon has 5 sides, an octagon has 8 sides. But how are they named? What's the name for a 248-sided polygon?

All polygons are suffixed with -gon. There are specific prefixes for each polygon depending on the number of sides. Here are the prefixes for the lower numbers:

3 - tri
4 - tetra
5 - penta
6 - hexa
7 - hepta
8 - octa
9 - nona
10 - deca
11 - undeca
12 - dodeca
13 - triskaideca
14 - tetradeca
15 - pentadeca
16 - hexadeca
17 - heptadeca
18 - octadeca
19 - nonadeca
20 - icosa

Polygons with 21 to 99 sides have a different system. Take the prefix for the tens digit (found on the left column), the ones digit (right column below), and then stick a "kai" between them to get (tens)(ones)gon.

20 - icosi       | 1 - hena
30 - triaconta   | 2 - di
40 - tetraconta  | 3 - tri
50 - pentaconta  | 4 - tetra
60 - hexaconta   | 5 - penta
70 - heptaconta  | 6 - hexa
80 - octaconta   | 7 - hepta
90 - nonaconta   | 8 - octa
                 | 9 - nona

The 3-digit sided polygons are named in a similar fashion. A 100-sided polygon is called a hectogon. Take the hundreds digit, find it on the column for ones digits, then stick a "hecta" to its right. Now number off the tens and ones like above: (hundreds)hecta(tens)(ones)gon. If the hundreds place digit is a 1, don't put the prefix behind "hecta".

So, given an integer (3 <= n <= 999), return the name of an n-sided polygon. n-gon is not a valid answer :P

As with all code golf, shortest code wins.


Is the description good? Would it be harder if I instead asked for the number of sides, given a name?

\$\endgroup\$
  • 1
    \$\begingroup\$ What is a 101-sided figure called? "hectahenagon"? Is "hena" from the column for ones digits you mention? If so, then what is a 111-sided figure called? I'd say "hectaundecagon", but then that comes from a column where "hena" is not present. \$\endgroup\$ – Gaffi Feb 11 '13 at 11:15
  • \$\begingroup\$ @Gaffi: Yep, it's hectahenagon, from what Google says. \$\endgroup\$ – beary605 Feb 11 '13 at 16:03
  • \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 4 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:43
  • \$\begingroup\$ I am going to take this if you allow me or if you don't respond \$\endgroup\$ – Christopher May 30 '17 at 1:13
2
\$\begingroup\$

Self-Golfing Code?

I don't know if I just didn't search hard enough, but I couldn't find any challenge regarding self-golfing code, or rather, any code that can deterministically reduce another set of text code to a much smaller program, yet still compile/run.

For example, take this:

int main() {
std::cout<<"Hello world 1!"<<std::endl;
std::cout<<"Hello world 2!"<<std::endl;
std::cout<<"Hello world 3!"<<std::endl;
std::cout<<"Hello world 4!"<<std::endl;
std::cout<<"Hello world 5!"<<std::endl;
}

And output this (as one possible solution):

#define A std::cout<<"Hello world 
#define B !"<<std::endl;
#define C B A
int main() {
A 1 C 2 C 3 C 4 C 5 B
}

Alternative:

Sub MySub()
Dim aNumber As Integer
Dim someString As String
aNumber = 123
someString = "abc"
MsgBox aNumber
MsgBox someString
End Sub

into (again, as one possible solution)

Sub m()
Dim a As Integer
Dim s As String
a = 123
s = "abc"
MsgBox a
MsgBox s
End Sub

Do we have a challenge for this?

If not, here are some rules I envision:

  • Golfing code need not be in the same language as code to be golfed.
  • Since compilers/running of code varies, newly golfed code must still run under same environment.
  • Possible challenge scoring (multiple options -- thinking code golf):
    • 1: Shortest golfing code wins (not my favorite, since you can minimally shorten the base code, yet still write the shortest program).
    • 2: Shortest output of a set of pre-defined code (potentially limiting if participants are unfamiliar with the options available)
    • 3: Combination of length of golfing code and the output result of the same as input. (Ratio, summation, etc.) -- This I think is my preferred option.
    • 4: Multi-player Ratio of golfed size of other participants' own code versus their original submission. (Similar limitations to that of point #2.)
\$\endgroup\$
  • 1
    \$\begingroup\$ Sounds more like an auto-golfer than obfuscation. Seems like it would be very hard to make it a fair contest unless you pick a language to golf, and even then it had better be a simple language (no platform dependency issues or compiler options). \$\endgroup\$ – Peter Taylor Feb 13 '13 at 15:15
  • \$\begingroup\$ @PeterTaylor My examples are golfing, but either would work. Perhaps golfing would be simpler, then? I agree that the options for usable languages makes this a bit messy... Would one challenge per language be acceptable? (i.e. aligned with most challenges that are language-agnostic) \$\endgroup\$ – Gaffi Feb 13 '13 at 17:36
  • 2
    \$\begingroup\$ Language-agnostic to mean means that you can write a program to do it in any language. Since the language to be golfed can be different from the submitted program, I don't see any incompatibility between making the problem "Write a program to golf Piet" and being language-agnostic. \$\endgroup\$ – Peter Taylor Feb 15 '13 at 0:18
  • \$\begingroup\$ @PeterTaylor So then you see no problem with one question per language on which to operate? Are there any proposed scoring algorithms you particularly like/dislike? \$\endgroup\$ – Gaffi Feb 15 '13 at 12:02
  • \$\begingroup\$ That depends on what you mean. If you're planning to post 10 questions at once, yes, that would be a problem. But I don't see a problem with posting a well-defined "Auto-golf Piet" and following it up two months later with "Auto-golf Perl 5". \$\endgroup\$ – Peter Taylor Feb 16 '13 at 10:19
  • \$\begingroup\$ Scoring is an issue. The halting problem means that it's impossible to write an optimal solution, so the scoring must take into account how good the solution is. I think option 3 is the best, and you'll want a big test set (maybe a few kB taken from a real-world open source project) with coverage of the language features. \$\endgroup\$ – Peter Taylor Feb 16 '13 at 10:22
  • \$\begingroup\$ Can we delete this because the sandbox lags so much and this hasn't been touched in 4 years? \$\endgroup\$ – programmer5000 Apr 13 '17 at 17:43
  • \$\begingroup\$ Btw, your first example doesn't work. You can't have unmatched quotes in preprocessor directives. Don't know why. \$\endgroup\$ – MD XF Jan 13 '18 at 18:03
  • \$\begingroup\$ I honestly think this would be fine if you did something like solely maco-golfing, making it somewhat language agnostic because of gcc -E. \$\endgroup\$ – Zacharý Nov 10 '18 at 14:36
2
\$\begingroup\$

DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>


I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

\$\endgroup\$
  • 2
    \$\begingroup\$ And the winning criterion is who is the first to get post from the courts? \$\endgroup\$ – celtschk Oct 3 '15 at 20:18
  • \$\begingroup\$ @celtschk, I think that would be unfair. Winning criteria shouldn't really depend on where people live... \$\endgroup\$ – Peter Taylor Oct 10 '15 at 20:56
  • 3
    \$\begingroup\$ I think you should at least explain the general concept of the spec. \$\endgroup\$ – Rohan Jhunjhunwala Aug 2 '16 at 22:53
  • \$\begingroup\$ This actually sounds interesting. @PeterTaylor Perhaps you could use (and link to) Charles Hannum's explanation of the algorithm and post this. (It would be fun to have it as a popularity contest for a program that looks like it's nothing DeCSS related, or a program that furthers the gallery's point about the text vs source code arbitrary distinction - but I don't know if popularity contests are popular any more!) \$\endgroup\$ – sundar Jun 25 '18 at 8:25
2
\$\begingroup\$

Missile Command

I'm making this CW, because it needs lots of help. I've been toying with this idea for a while. Think "battleship" to get in the right mind-frame. But, instead of ships, what you lay down are tiles which represent a Befunge-style program. This program controls the behavior of guided missiles ejected from the spawn tile. The goal is to program a missile which will obliterate an opponent's program block, as well as guard its own control block.

Haven't nailed-down the board size. 20x20 seems a little cramped.

         1         2
12345678901234567890
____________________1  4x20 program block
____________________2
____________________3
_______@____________4
....................5  12x20 arena
....................6
....................7
....................8
....................9
....................01
....................1
....................2
....................3
....................4
....................5
....................6
___________@________7  4x20 program block
____________________8
____________________9
____________________02

Tiles

@ spawn

Program control.

I'm imagining these to change direction of the code for "boustrophedon" writing.

this,then\
 txen,siht

haven't thought it all though, yet.

/

\

Movement.

F forward move forward one square

B back move back one square

L left turn left 90°

R right turn right 90°

So the submissions would be 4x20 code blocks which compete in a king-of-the-hill style.

\$\endgroup\$
  • \$\begingroup\$ If this is deterministic, won't it be "Last person to submit their program wins"? \$\endgroup\$ – Peter Taylor Jun 7 '13 at 8:39
  • \$\begingroup\$ That is a danger, yes. I'm hoping ways around it can be found. There could be a random operator. And proximity detection, or something. \$\endgroup\$ – luser droog Jun 7 '13 at 8:46
2
\$\begingroup\$

Code golfing problem: Surface classification

The task: Given a surface-word reply with the classification of what surface it is.

Example 1: Input: aba'b' ----> Output: 1T

Example 2: Input: aabcb'c' ----> Output: 3P

Bounds on the problem: Since there are only 26 letters, there will never be more than that many labels. Additionally output should be in the form S,nT,mP for n,m positive integers.

Background: In the study of algebraic topology students are often presented with diagrams such as the one below. The represent instructions for how to assemble a surface. The assembly is prescribed as: if there are two edges labeled with the letter x then glue them together so that the arrows point the same direction. To make our job easy, topologists have discovered an algorithmic way to classify surfaces using 'words' assembled from these 'plane gluing-diagrams'.

enter image description here Choosing a corner arbitrarily (top right) and orientation (ccw) we read off the labels on the edges where an inverse appears wherever the arrow points against the orientation. In this case the 'word' that represents this plane model is given as abab.

A surface word is a string that contains the letters a,b,...,@ up to some letter @ and each letter is contained in it exactly twice. In the two occurrences of each letter: 0, 1, or 2 of them may be postfixed by a ' which I am considering using to represent 'inverse' (opposite orientation).

If in a surface word all letters appear twice: once without the ' and once with it (f.ex. ba'b'a) then we say that the surface the word represents is orientable. If a surface is orientable then it is necessarily the direct sum of n Tori for some non-negative integer n. If this condition doesn't hold (like in aab'b) then the surface represented is non-orientable: in this case it is the direct sum of m Projective Planes for some positive integer m.

Once you have found out if the reduced word is orientable or not, the final answer is given as follows. If orientable and number of unique letters in the reduced word is 1 then output should be S. Otherwise if the number of unique letters in an orientable word is n (it will be even) then the output should be sT where s = n/2. If the word is non-orientable then the output should be mP where m is the number of distinct letters in the reduced word.

The goal is to take as input some surface word, reduce it via reduction rules 1-6 and then classify it as a sphere, some number of connected tori, or some number of connected projective planes. Here are the 6 reduction rules where ~ represents 'reduces to':

Let M,A,B,C,D be surface words, x be a single letter, and juxtaposition represents concatenation:

  1. Cycle Rule: If M = AB then M ~ BA
  2. Flip Rule: M ~ M'
  3. Sphere Rule: Axx'B ~ AB
  4. Block Rule: ABC ~ ADC if B is a surface word and B ~ D by 1 or 2
  5. Cylinder Rule: If M = AxBCx'D, then M ~ AxCBx'D
  6. Möbius Rule: If M = AxBxC then M ~ AxxB'C ~ AB'xxC

I am looking for input on:

  • should this be code-golf or programming-challenge?
  • how would scoring work?
  • ???

If I feel satisfied with the question in a few days I'll post it to the site.

\$\endgroup\$
  • \$\begingroup\$ If, for each input, there is only one correct output, then it should probably be code-golf. The scoring criteria would then be source code length. \$\endgroup\$ – PhiNotPi Jun 8 '13 at 14:33
  • \$\begingroup\$ Yes, this is the case. In general however there is not a unique series of applications of the reduction rules for any given instance. \$\endgroup\$ – Kaya Jun 8 '13 at 16:21
  • \$\begingroup\$ I don't think the order of explanation is correct. You should explain reduction before talking about "the reduced word". And "reduce it via reduction rules" doesn't entirely make sense, because the rules are presented as equivalences rather than reductions, and most of them don't have a "natural" direction. \$\endgroup\$ – Peter Taylor Jun 10 '13 at 8:49
  • \$\begingroup\$ It's also occurred to me that you haven't defined the notation M'. Does it just consist of toggling the orientation of each token, or does it also reverse the entire string? And do you have test cases which between them force implementation of all of the reduction rules? \$\endgroup\$ – Peter Taylor Jun 11 '13 at 8:32
  • \$\begingroup\$ Good call on the string inverse, yes you have the right idea and I will make it clear. I have a lot of test cases from when I did a number of these computations by hand in a university course and (anecdotal experience) I am pretty sure that it is possible to force the use of all the reduction rules (except maybe 4 which is really just a meta-rule for convenience when doing proofs). Additionally you have alerted me to some concerns regarding the form of the proper output: it's definitely underspecified. I'll put some work into this today. \$\endgroup\$ – Kaya Jun 11 '13 at 14:04
2
\$\begingroup\$

Find all of the Scrabble numbers:

A scrabble number is a number n whose scrabble representation can score n points. As an example consider 12: its English spelling twelve has value 12 when it is placed on a stretch of six blank tiles. Since the highest ever reported 1 word scrabble score barely exceeds 2000 points, that will be the upperbound for this challenge.

Score and quantities for English:

2 blanks |  x1  |  x2  |  x3  |  x4  |  x6  |  x8  |  x9  |  x12 |
    1    |      |      |      | LSU  | NRT  | O    | AI   | E    |
    2    |      |      | G    | D    |      |      |      |      |
    3    |      | BCMP |      |      |      |      |      |      |
    4    |      | FHVWY|      |      |      |      |      |      |
    5    | K    |      |      |      |      |      |      |      |
    8    | JX   |      |      |      |      |      |      |      |
   10    | QZ   |      |      |      |      |      |      |      |

Considerations for either bonus points to scoring or extra requirements:

  • Respect the board, only using gaps between double/triple letter and double/triple word scores that occur on a standard scrabble board.
  • Respect the tile count for each letter.
  • There are non-English versions of scrabble, maybe it should be 'language-agnostic' (lol, but seriously is there a reason to accept only English submissions?).
  • Should the 2 blanks be allowed?
\$\endgroup\$
  • \$\begingroup\$ What about tiles which were already on the board and so wouldn't score anything? As for language: one approach would be to make it take the names of the tiles (and perhaps the values and counts of the letters) as input; this would also prevent the problem from being effectively one of Kolmogorov complexity. \$\endgroup\$ – Peter Taylor Jun 19 '13 at 22:50
  • \$\begingroup\$ I don't believe that tiles on the board already would pose an issue. If you assume that the board may be prepared with any subset of the tiles beforehand (some may be impossible, but checking that is out of scope) all that is relevant to the problem is which are placed to complete the word. All the tiles points are counted, even the earlier placed, but only the new 7 (or less) tiles may qualify for triple/double-word/letter scores. w.r.t. kolmogorov, If I wanted to make it programming challenge instead of codegolf (so that isn't an issue) then there needs to be a scoring system right? \$\endgroup\$ – Kaya Jun 19 '13 at 23:33
  • \$\begingroup\$ Yes, if it isn't codegolf then it needs a scoring system. I'm not sure what you could use as an alternative scoring criterion, though: it's simple enough logic that pretty much any implementation would be IO-bound, so speed doesn't work; and big-O based tends to be less straightforward than you might think. \$\endgroup\$ – Peter Taylor Jun 21 '13 at 11:05
2
\$\begingroup\$

Sort all lines according to their corresponding Levenshtein Distance to the first line.

Shamelessly borrowed from: http://golf.shinh.org/p.rb?Levenshtein+Distance+Sort+FIXED

For a definition of the Levenshtein Distance, look here: http://en.wikipedia.org/wiki/Levenshtein_algorithm

Rules:

Takes input from stdin. Must work for all possible input. Get points for:

Smallest character count. Using Languages that are difficult to golf in. I think character count / the average values from here (http://golf.shinh.org/lranking.rb) might suffice?

\$\endgroup\$
  • \$\begingroup\$ There are a number of ambiguities in the problem description. What is the correct behaviour if the input is empty? In the general case, should the first line be included in the lines which are sorted and output? Should the sort be by ascending or descending edit distance? How should ties be broken? \$\endgroup\$ – Peter Taylor Jun 25 '13 at 20:23
  • \$\begingroup\$ As for handicapping: are you going to prohibit built-in or library-provided edit distance functions? If not then the averages you link are not especially relevant: PHP handily wins the existing edit distance question by virtue of its built-in function. \$\endgroup\$ – Peter Taylor Jun 25 '13 at 20:27
  • \$\begingroup\$ (That existing question does also raise the possibility of yours being closed for not being sufficiently different). \$\endgroup\$ – Peter Taylor Jun 25 '13 at 20:28
2
\$\begingroup\$

Fastest Code: checking if interval pairs overlap

Given an unsorted input of many interval pairs (50+), write the fastest algorithm to determine if they do not overlap.

An interval pair is said to overlap if interval x and interval y are overlapping.

Example input 1:
interval x , interval y

10-25, 50-60
10-15, 25-60

Output:
Can be in any true false format.

false (They overlap)

reasoning:

a.x overlaps b.x
a.y overlaps b.y

Example input 2:

10-25, 50-60
20-30, 25-30

Output:

true (they do not overlap)

reasoning:

a.x overlaps b.x
a.y does not overlap b.y

Scoring:

[not sure...]
brute force gives a worst case n^2 runtime
\$\endgroup\$
  • 1
    \$\begingroup\$ It's hard to understand what the program is supposed to do. It's better to give three separate self-contained test cases than to mix them together with extra identifiers which won't be in the actual input. But if I understand correctly, there's nothing difficult here at all. It's just interval overlap testing (two ifs) done twice for no obvious reason. \$\endgroup\$ – Peter Taylor Jul 5 '13 at 19:45
  • \$\begingroup\$ The problem is that there will be a very large input. I'm thinking > 50 lines. \$\endgroup\$ – EAKAE Jul 5 '13 at 20:50
  • \$\begingroup\$ I'm not sure whether or not to score it based on time, or worst case runtime. \$\endgroup\$ – EAKAE Jul 5 '13 at 20:59
  • 1
    \$\begingroup\$ Instead of asking for overlap, ask for disjoint: "Check if a family of intervals is disjoint". I also think it would be more interesting if you give intervals in interval notation but I you should at least specify whether or not the endpoints are included. \$\endgroup\$ – Justin Dec 21 '13 at 7:41

You must log in to answer this question.

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