477
\$\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 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – James Aug 29 '19 at 15:19
  • 3
    \$\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 '19 at 13:43

2846 Answers 2846

1
11 12
13
14 15
95
3
\$\begingroup\$

Join by intersection

Given a list of strings, output these strings joined by their largest intersecting parts. Your output has to be optimal. Strings have to be joined in the order given.

What is an intersection anyway?

Suppose you have two strings:

"abcbc" "bcbcd"

You extract all suffixes of the first string, as well as all prefixes of the second string:

["abcbc", "bcbc", "cbc", "bc", "c"]
["bcbcd", "bcbc", "bcb", "bc", "b"]

We trunctuate both of these lists to the length of the list of the smaller length (it's an identity in this current case).

Then, we find all items at the same index which are equal to the other item at the same index:

["bcbc", "bc"]
["bcbc", "bc"]

We return the longest string of the output. Therefore, the intersection is:

"bcbc"

How to join two strings by the intersection

To join by the intersection you simply

  1. Append the first string without the intersection to the output string
  2. Append the intersection to the output string
  3. Append the second string without the intersection to the output string

For example, in our example case:

"abcbc" "bcbcd"
(The intersection is "bcbc")

Step 1. Out:"a"
Step 2. Out:"abcbc"
Step 3. Out:"abcbcd"

Reducing a join over a list

If you want to reduce a join over a list

["abc","bcd","rfh","hal"]

You connect them by their longest common substring:

abc
 bcd
    rfh
      hal
=========
abcdrfhal

Therefore the expected output is abcdrfhal.

Further walkdown

You cannot join two strings if their substring can be found in the middle. For example:

["aXc","bXd"]

If you try to match them by the middle substring:

aXc
bXd

You would realize that the other overlapping characters are not equal to each other. That is, a is not equal to b, and c is not equal to d. In that case you simply append the string in the join:

aXc
   bXd
======
aXcbXd

Likewise, if either of these strings contain each other, but isn't equal to the other string, you should simply append the string. E.g.

["abcd","bc"]

would give

abcd
    bc
======
abcdbc

Substrings can overlap past each other. E.g.

["abc","bcd","cde"]

would result in the following join:

abc
 bcd
  cde
=====
abcde

which would evidently make the output abcde.


Strings have to overlap as much as possible. That means, in this example:

["abcbc","bcbcd"]

This is not okay (even if they do overlap):

abcbc
   bcbcd
========
abcbcbcd

Instead, this should be done:

abcbc
 bcbcd
======
abcbcd

The join is consecutive based on the consecutive inputs. For example:

abcde
  cde
     abcde
==========
abcdeabcde

Test cases

A program is worth a thousand words. Here 's a reference implementation that I use to check the test cases.

["abc","bcd","rfh","hal"] -> "abcdrfhal"
["mmm","qqq","rrr"] -> "mmmqqqrrr"
["abcbc","bcbcd"] -> "abcbcd"
["aXc","bXd"]    -> "aXcbXd"
["abc","bcd","cde"] -> "abcde"
["abcd","bc"] -> "abcdbc"
["abcde", "cde", "abcde"] -> "abcdeabcde"
| |
\$\endgroup\$
  • \$\begingroup\$ How would you join aXc and bXd? They have the common substring X in the middle. \$\endgroup\$ – Bubbler Mar 25 at 2:24
  • \$\begingroup\$ Can strings overlap past each other like abc,bcd,cde->abcde? \$\endgroup\$ – xnor Mar 25 at 2:25
  • \$\begingroup\$ Do strings have to overlap as much as possible, or just overlap any amount? For example, for abcbc and bcbcd, is either of abcbcd or abcbcbcd OK? \$\endgroup\$ – xnor Mar 25 at 4:43
  • \$\begingroup\$ Do strings have to be joined in the order given? I feel like the answer is surely "yes", but the text doesn't say outright. Really, I think all these Sandbox questions come from the fact that the task is never actually stated precisely, and doing that would probably head off any further question. \$\endgroup\$ – xnor Mar 25 at 4:49
  • 2
    \$\begingroup\$ Along these lines, what happens if one string contains another? Do we do abcd,bc->abcd? \$\endgroup\$ – xnor Mar 25 at 4:51
  • \$\begingroup\$ Suggested test case: abcde, cde, abcde. \$\endgroup\$ – Jonathan Frech Mar 25 at 4:52
  • \$\begingroup\$ @JonathanFrech Well, what's the expected output? I thought it was abcde in this case. \$\endgroup\$ – Λ̸̸ Mar 25 at 6:00
  • \$\begingroup\$ I was not completely sure what the output would be. abcdeabcde does seem reasonable. \$\endgroup\$ – Jonathan Frech Mar 25 at 7:40
  • 2
    \$\begingroup\$ I still don't actually understand how the task works precisely. A reference implementation isn't a replacement for a specification. \$\endgroup\$ – xnor Mar 25 at 23:09
  • \$\begingroup\$ @xnor I've added back the spec, can you understand it now? \$\endgroup\$ – Λ̸̸ Mar 26 at 6:24
  • \$\begingroup\$ Not really, sorry. I still wouldn't know what abcd,bc would give. \$\endgroup\$ – xnor Mar 26 at 6:29
  • \$\begingroup\$ @xnor Are there any more test cases you don't understand? \$\endgroup\$ – Λ̸̸ Mar 26 at 6:35
  • \$\begingroup\$ This seems to be related to the shortest superstring problem for two strings, but you don't have to handle the case where one of the strings is a substring of another, and the joining order is fixed. Is that correct? Just informing that the specification spans four pages on my laptop, with default browser font size. \$\endgroup\$ – my pronoun is monicareinstate Mar 26 at 6:55
  • \$\begingroup\$ @a'_' en.wikipedia.org/wiki/… \$\endgroup\$ – my pronoun is monicareinstate Mar 26 at 6:58
  • \$\begingroup\$ @mypronounismonicareinstate Ah, it's a duplicate. Thank you for the mention. \$\endgroup\$ – Λ̸̸ Mar 26 at 6:58
3
\$\begingroup\$

Sum in 2540 Sums

This is my attempt to pair with .

You need to write a program that sums all codepoints of the input string.

Rules

  • The input will always be in printable ASCII.
  • The sum of the codepoints of your source must be exactly 2540.

    • You are allowed to use your language's own code page to calculate your program's codepoints.
  • Null bytes (which don't contribute to your codepoint sum) are banned.

  • The program must not work with any consecutive substring removed.
  • This is . Your score is the length of your source code, the shorter being better.
| |
\$\endgroup\$
  • \$\begingroup\$ You defined the "base score" only to reference that term exactly once. It seems to be move confusing than helpful. Wouldn't "The sum of the codepoints of your source must be exactly 2540" be clearer and shorter? \$\endgroup\$ – Ad Hoc Garf Hunter Apr 9 at 21:18
  • \$\begingroup\$ Although I am neither suggesting nor recommending against, this could also work as code-bowling if you either outlaw null bytes or sum up the (codepoints+1). \$\endgroup\$ – Ad Hoc Garf Hunter Apr 9 at 21:22
  • \$\begingroup\$ @AdHocGarfHunter The rules are a lot simpler if it were code-golf, and we haven't paired codepoint sum with code golf before. Also I need to fullfill a goal to pair code-bowling with code-golf. This analysis says that there are 11 tags not paired with code-golf, I'm going to make it 10. \$\endgroup\$ – Λ̸̸ Apr 9 at 21:24
  • \$\begingroup\$ As far as I know, [pristine-programming] is the tag for programming with the substring removal restriction here. (I think this would work as a [code-bowling] as well as well) \$\endgroup\$ – my pronoun is monicareinstate Apr 10 at 0:12
  • \$\begingroup\$ @mypronounismonicareinstate So which side are you for? Code golf or code bowling? \$\endgroup\$ – Λ̸̸ Apr 10 at 0:53
  • \$\begingroup\$ Probably code-golf. \$\endgroup\$ – my pronoun is monicareinstate Apr 10 at 1:07
3
\$\begingroup\$

Fold my ACGT proteins

Quoting Wikipedia, "Protein folding is the physical process by which a protein chain acquires its native 3-dimensional structure, a conformation that is usually biologically functional, in an expeditious and reproducible manner.". I don't know what that means but by means of a game called Foldit it seems we can use protein folding in some way to help and fight diseases.

Please bear in mind that the task described was inspired by the isolated meaning of the words in "protein folding" and doesn't necessarily translate into how protein folding really works! i.e. the title is just a pun.

Task

Your task is to take a string matching the regex /^[ACGT]+$/ and return the number of times the string can be "folded". A string can be folded if and only if:

  • It's length is even;
  • The first half of the string is the reverse of the second half of the string.

Input

Acceptable input formats include but are not limited to:

  • strings
  • character lists
  • codepoint lists

Output

The output is an integer; I don't think there's much room to wiggle here, but let me know if you really wanted to return something else.

Test cases:

Python reference implementation

'A' -> 0
'AAA' -> 0
'AAAAA' -> 0
'TAAAAAAA' -> 0
'ATAAAAAA' -> 0
'AATAAAAA' -> 0
'AAATAAAA' -> 0
'AAAATAAA' -> 0
'AAAAATAA' -> 0
'AAAAAATA' -> 0
'AAAAAAAT' -> 0
'TGCAACGTTGCAACGT' -> 2
'ACGTTGCAACGTTGCAACGTTGCAACGTTGCA' -> 3
'TGCAACGTTGCAACGTTGCAACGTTGCAACGTTGCAACGTTGCAACGTTGCAACGTTGCAACGT' -> 4
'TACCCCATTACCCCAT' -> 2
'TTTT' -> 2
'TATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTATTAT' -> 5
'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA' -> 6
'CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC' -> 6
'GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG' -> 6
'TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT' -> 6
'TAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAATTAAT' -> 5
'GCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCGGCCG' -> 5
'CATTACCATTACCATTACCATTAC' -> 3
'CATTACCATTACCATTACCATTAC' -> 3
'CATACCATACCATACCATACCATACCATACCATACCATAC' -> 3
| |
\$\endgroup\$
  • \$\begingroup\$ Where did you get the "The first half of the string is the reverse of the second half of the string." requirement from? \$\endgroup\$ – Lyxal Apr 28 at 0:25
  • \$\begingroup\$ @Lyxal I do not understand the question \$\endgroup\$ – RGS Apr 28 at 5:58
  • \$\begingroup\$ Protein folding is usually related to amino acids, which are based on groups of 3 nucleic bases. And usually, it doesn't really matter what order they are in. I say this because the ATCGs you have aren't amino acids. They are nucleic bases which, when converted into RNA (which uses U instead of T) become amino acids. \$\endgroup\$ – Lyxal Apr 28 at 6:15
  • \$\begingroup\$ @Lyxal ah I understand what you mean. I have added this sentence: Please bear in mind that the task described was inspired by the isolated meaning of the words in "protein folding" and doesn't necessarily translate into how protein folding really works. This addresses your issue, right? Also, this probably means the tag you added doesn't really make sense here, no? What do you think? (On the other hand if you know how PF works I'm glad to talk with you to forge a more closely related challenge) \$\endgroup\$ – RGS Apr 28 at 6:20
  • \$\begingroup\$ it's been a while since I last studied PF, but if it's an isolated meaning/simplified approach, then that seems fine to me. \$\endgroup\$ – Lyxal Apr 28 at 6:23
  • 4
    \$\begingroup\$ I think it's just a pun isn't it? Not literally "folding" proteins in the usual complicated 3 dimensional fashion, but just folding them a string supposedly representing a protein in half. \$\endgroup\$ – Steve Bennett Apr 30 at 7:08
  • \$\begingroup\$ @SteveBennet dang it! I missed the joke. \$\endgroup\$ – Lyxal May 1 at 23:54
3
\$\begingroup\$

Posted here: The first digit of a to the power of b (approximately)

| |
\$\endgroup\$
  • \$\begingroup\$ To do math formatting you can use \$latex in here\$ \$\endgroup\$ – Command Master Apr 18 at 14:18
  • \$\begingroup\$ Any more comments before I post it? \$\endgroup\$ – simonalexander2005 Apr 21 at 8:22
  • \$\begingroup\$ The test cases could be formatted in a single block to allow for easy copy/paste \$\endgroup\$ – math junkie Apr 23 at 18:10
  • \$\begingroup\$ How's that? I've added a sample implementation too - although not one that contains all the examples... \$\endgroup\$ – simonalexander2005 Apr 24 at 9:18
  • \$\begingroup\$ Sorry, I don't understand the doRounding column of the test cases. Is that an additional input? If so, it's not mentioned in the "inputs" section. \$\endgroup\$ – math junkie Apr 24 at 16:17
  • \$\begingroup\$ In the worked example at the top, in the "background" section, I mention that at each stage when you truncate the number, you can round or not at your discretion - so I've included both options in the examples. Does that make sense? For example 6561 * 6561 = 43046721 - if 4 is our truncating factor you could take 4304, or you can round to 4305 (because 43046 is closer to 4305 than 4304) - is that clear? Is it too confusing to offer both options? \$\endgroup\$ – simonalexander2005 Apr 24 at 17:35
  • \$\begingroup\$ I suppose that means that each test case has 2 possible outputs? Maybe you could list both possible outputs instead of having the doRounding column (to make it clear which is which, you could have one column that is "output with rounding" and one that is "output without rounding") \$\endgroup\$ – math junkie Apr 24 at 17:55
  • \$\begingroup\$ that makes sense. Should I just pick one output instead though - what's best? I like the rounding because it is more accurate, but it's an extra step that doesn't seem related to the challenge. HMm... \$\endgroup\$ – simonalexander2005 Apr 26 at 11:28
  • \$\begingroup\$ I have updated to make rounding mandatory. Will post next week if no further comments and I remember... \$\endgroup\$ – simonalexander2005 May 1 at 7:31
  • \$\begingroup\$ @mypronounismonicareinstate better? \$\endgroup\$ – simonalexander2005 May 1 at 13:12
3
\$\begingroup\$

Posted.

| |
\$\endgroup\$
  • \$\begingroup\$ For the sake of completion: can I give my output as a list of strings? \$\endgroup\$ – Lyxal Apr 29 at 23:02
  • \$\begingroup\$ @Lyxal Seeing as that's a generally accepted I/O method, yes. \$\endgroup\$ – sporeball Apr 30 at 0:09
3
\$\begingroup\$

Is this a half-sort?

The problem over here introduces an new type of strings: if you split the string into equal halfs and swap the pairs, it produces the same output as sorting the string. We call that a half-sort.

Given a purely ASCII string, check if the string is in a half-sort.

An example of a half-sort string

The string node is a half-sort string, because if you sort by codepoints (note that the codepoints are in decimal, not binary):

n 110
o 111
d 100
e 101

That gets turned into:

d 100
e 101
n 110
o 111

You'll see that the node to deno conversion is exactly moving the right half to the left position.

Specification

  • For odd-length strings, splitting should make the first half longer.
  • Sorting a string means sorting the string based on the codepoints of the characters.

Reference program & test cases

Here is the reference program I made for checking my test cases.

node -> True
rum  -> True

deno -> False
rim  -> False
```
| |
\$\endgroup\$
  • \$\begingroup\$ @mathjunkie then the codepoints given are incorrect. \$\endgroup\$ – Lyxal May 24 at 22:43
  • \$\begingroup\$ @Lyxal Why are they incorrect? I wrote a program to generate the codepoints. \$\endgroup\$ – Λ̸̸ May 25 at 8:15
  • \$\begingroup\$ Oh wait. I thought they were in binary. \$\endgroup\$ – Lyxal May 25 at 8:18
  • \$\begingroup\$ As in, you were using the binary representation of each ordinal value. \$\endgroup\$ – Lyxal May 25 at 8:19
  • \$\begingroup\$ @Lyxal No. I was using the decimal expansion of the ord codes. I am going to clarify that. \$\endgroup\$ – Λ̸̸ May 25 at 8:19
  • \$\begingroup\$ I cam see that now. I just assumed those numbers were base 2,rather than base 10 \$\endgroup\$ – Lyxal May 25 at 8:20
  • \$\begingroup\$ Seems pretty clear, but would benefit from test cases with odd-length strings. For example, 'rim' (false) and 'rum' (true) illustrate the 'first half longer' splitting rule. (Truthiness for these two words would be swapped if the rule were second half longer.) \$\endgroup\$ – Dingus May 29 at 7:24
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\$
  • 10
    \$\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 --- ex-moderator kitten 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\$

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
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\$

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
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 - Reinstate Monica Jun 25 '18 at 8:25
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\$

Business Card Ray Tracer

I have no idea how to create a good code golf question!

See this description of a ray tracer with source code that fits on a business card. The author stopped when the code size was 1337 bytes.

http://fabiensanglard.net/rayTracing_back_of_business_card/index.php

Achieving identical output, optimise for minimum code size. Execution time is not relevant.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think what you have here is a straight ahead golf. All languages. You need only define the requirements. Do you want identical output or do you want "good output encompassing <list of features>"? \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 6 '13 at 17:22
  • 1
    \$\begingroup\$ For a minimum feature list I'd suggest something like (1) it is ray tracer (2) supports point-like lights and shadow + ambient light (3) supports mirrored (implies reflection) and matte surfaces (3) all objects are sphere and overlaps are allowed. With no requirement for (a) anti-aliasing; (2) finite sized light sources; (c) atmosphere effect or (d) depth of field; or (e) tiling and gradients. Notice however, that the example supports at least (b), (d) and (e). \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 6 '13 at 17:29
  • 1
    \$\begingroup\$ BTW--The one you linked can get a little bit more with #define Q return (R was already taken for the rand wrapper) and #define O operator. \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 6 '13 at 17:33
  • 3
    \$\begingroup\$ I suggest reading the Teapot question in the sandbox Mk IV and the comments - it's not the same question, but some of the same issues are relevant, and it might give you ideas for improvements to the spec. \$\endgroup\$ – Peter Taylor Oct 6 '13 at 22:48
  • \$\begingroup\$ Yes. Read the teapot question for guidance. Ultimately I decided that one was too big, but we did get into some pertinent details. \$\endgroup\$ – luser droog Dec 1 '13 at 9:48
  • \$\begingroup\$ This sandbox post has had little activity in a while and little positive reception from the community. Please improve / edit it or delete it to help us clean up the sandbox. \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:32
2
\$\begingroup\$

Count unique characters in text.

Given a string for input, output the unique non-whitespace characters in that string along with a count of their occurrences. The list should be sorted in ascending order of ASCII code.

Examples

Input:

Hello, World!

Output:

Character    Count
!            1
,            1
H            1
W            1
d            1
e            1
l            3
o            2
r            1

Input:

The quick brown fox jumps over the lazy dog.

Output:

Character    Count
.            1
T            1
a            1
b            1
c            1
d            1
e            3
f            1
g            1
h            2
i            1
j            1
k            1
l            1
m            1
n            1
o            4
p            1
q            1
r            1
s            1
t            1
u            1
v            1
w            1
x            1
y            1
z            1

The actual formatting (headers, spacing, etc) of the on-screen output is up to you. The only conditions are that it must be sorted in ascending order by ASCII code, and it must be easy to tell what represents a character from the string and what represents a count of a given character. (For example, given a string of 99999999, the output should be explicit so that it is not confused as saying I have 9 8s.)

Ultimate challenge (taken from here):

JKqdJg+oJgiowgyIJgkS+gyxJdeS+gyxJ4yoJdybJdioJdqIJ4kS+KwFJ4QS+gzYJg+ow4vIJ4yxvd+IJgy=+dv=JdQx+gzbJrzx24zYJgkxJ4qLJKQxJ4yxJKqx+KqdJKqdJg+oJgiowgyIJgkS+gyxJdeo24yxJm+xJdybJdioJdqIJKi=J4wF+dvS+gzYJg+ow4zYJ4yxvdy=J4i=+Kv=JdQo+KqxJrzdJKzYJgkxJ4qLJgkxJ4yxJKvSJ4qbJKqdJg+oJgiowgyIJgkdJgyxJdeo24yxJm+xJdybJd+oJd+S+dz=J4wF+dvS+g+SJg+ow4vIJ4yxJ4voJgy=+dv=+dzdJgqxJrzdJKzYJgkS+dweJKQxJ4yxJKvSJ4qbJKq=24yYJgiowgyIJgkdJgzdJryo24yxJm+d24zxJd+oJdqIJ4kS+KwFJ4QS+gzYJ4y=2gzYJ4yxJ4voJgy=+dv=+dzdJgqxJrzx24zYJgkS+dweJKQxJ4fK+dQSJ4qbJKq=24yYJgiowgyIJgkS+gzdJryS+gyxJ4yoJdybJd+oJd+S+dz=J4wF+dvS+gzYJ4y=2gvIJ4yxJ4voJgy=+dv=JdQo+KqxJrzx24zY+dzS+dweJKQxJ4yxJKqx+KqbJKq=24vbJdyowgyIJgkdJgzdJryS+gyxJm+d24zxJdioJd+S+dz=J4wF+dvS+gzYJg+ow4vIJ4yxJ4voJgy=+Kv=JdQx+gzbJrzx24zYJgkS+dweJgkxJ4yxJKvSJ4qdJKq=24yYJgiowgyIJgkdJgzdJryS+gyxJ4yoJdybJd+oJdqIJKi=J4wF+dvS+gzYJg+ow4vIJ4yxJ4v=J4i=+Kv=+dzdJgqxJrzx24zYJgkS+dweJgkxJ4fKJ4qx+KqdJKqdJg+SJdyowg+oJgkS+gyxJdeS+gyxJ4yoJdybJd+oJdqIJ4kS+KwFJ4QS+g+SJ4y=2gzYJ4yxJ4v=J4i=+Kv=JdQo+KqxJrzx24zY+dzS+dweJKQxJ4yxJKvSJ4qbJKqdJg+oJgiowg+oJgkS+gzdJryo24yxJ4yoJdybJdioJdqIJ4kS+KwFJ4QS+g+SJg+ow4vIJ4yxvd+IJgy=+dv=JdQo+KqxJrzdJKzY+dzxJ4qLJKQxJ4yxJKqx+KqdJKq=24vbJdyowg+oJgkS+gzdJryo24yxJ4yoJdybJdioJd+S+dz=J4wFJ4QS+gzYJg+ow4zYJ4yxvd+IJgy=+Kv=+dzdJgqxJrzdJKzYJgkxJ4qLJgkxJ4yxJKvSJ4qbJKq=24vbJdyowgyIJgkdJgyxJdeo24yxJm+xJdybJd+oJdqIJKi=J4wF+dvS+g+SJ4y=2gvIJ4yxvd+IJgy=+dv=+dzdJKzbJrzdJKzY+dzS+dweJgkxJ4yxJKvSJ4qbJKq=24yYJgiowg+oJgkS+gyxJdeo24yxJ4yoJKzxJd+oJdqIJKi=J4wF+dvS+gzYJg+ow4vIJ4yxJ4v=J4i=+dv=+dzdJgqxJrzx24zYJgkxJ4qLJKQxJ4fKJ4qx+KqdJKqdJg+oJgiowgyIJgkS+gzdJryS+gyxJm+d24zxJd+oJdqIJKi=J4wFJ4QS+gzYJ4y=2gzYJ4yxvdy=J4i=+Kv=+dzdJKzbJrzx24zY+dzxJ4qLJKQxJ4yxJKqx+KqdJKqdJg+SJdyowg+oJgkdJgzdJryo24yxJm+d24zxJd+5

| |
\$\endgroup\$
  • \$\begingroup\$ This isn't really an interesting problem. The shortest answer is almost certainly going to be fewer than 10 characters. \$\endgroup\$ – Peter Taylor Dec 11 '13 at 12:19
  • \$\begingroup\$ @PeterTaylor While I mostly agree with your comment - already the header line may contain more than 10 characters. \$\endgroup\$ – Howard Dec 12 '13 at 6:15
  • \$\begingroup\$ "The quick brown fox jumps over the lazy dog." contains "e" three times. \$\endgroup\$ – Howard Dec 12 '13 at 6:16
  • \$\begingroup\$ @Howard Thanks. I must be blind - it took me about five times of reading your comment to find it. Also, do remember that the header is optional to a certain degree - you just need to make sure the output is unambiguous as to which items are characters from the string, and which are character counts. \$\endgroup\$ – Iszi Dec 12 '13 at 7:02
  • \$\begingroup\$ My brain instantly went into bash mode. wc and uniq practically solve half of this, but not in any particularly short manner. \$\endgroup\$ – Rob Dec 17 '13 at 20:31
2
\$\begingroup\$

PETSCII banner

PETSCII on CodGolf.StackExchange

In an other world... I was using a PET 2001 who used some particular PETSCII charset.

The screen green on black, with 40 columns and 25 lines, was only able to display characters from this charset. No way to draw dots or lines...

But in the chaset, there is some and , which, ( by the use of reverse video in order to obtain 16 chars: ' ','▖','▗','▘','▝','▀','▄','▐','▌','▞','▚','▟','▛','▜','▙','█' ) make us able to draw graphics on a 80x50 dots plan.

Using an internal clock triggering IRQ, I've done a animated prompter like this:

Animated display sample Hello world!

The goal of this is to make a similar banner, with same charset, (but using UTF-8 characters: ' ','▖','▗','▘','▝','▀','▄','▐','▌','▞','▚','▟','▛','▜','▙','█'). Warn, this charset use inverted lower/upper cases.

  • This imply the use of PETSCII charset, I will post them there as a json string, before getting this out of the sandbox if some interest...

  • The tool have to change his position 20 time per second.

  • The tool must accept as argument, the string to display.

  • The tool must add date and time in the form - WDay MDay Mnth Year, HH:MM:SS -

  • Scrolling have to be done bit per bit: I.E.: by half character!

  • Shortest code...
    • -3 if size of console is not limited to 40 columns
    • -5 if cpu usage stay less than 90% (On my poor Core(TM)2 Duo CPU E8400 @ 3.00GHz, with 4G ram)
    • -5+ if cpu usage stay less than 50%
    • -5+ if cpu usage stay under 5%

C.U.

| |
\$\endgroup\$
  • 3
    \$\begingroup\$ as for the CPU bonuses - what is the target environment, what is the smoothing factor, and what processes count against this measure? \$\endgroup\$ – John Dvorak Dec 15 '13 at 6:19
  • \$\begingroup\$ This sandbox post has had little activity in a while and little positive reception from the community. Please improve / edit it or delete it to help us clean up the sandbox. \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:32
2
\$\begingroup\$

This is my first try at writing a challenge. Please let me know how I can improve it.

Roman Calculator

Create a basic calculator for Roman numerals.

Requirements

  • Supports +,-,*,/
  • Input and output should expect only one prefix per symbol (i.e. 3 can't be IIV because there is two I's before V)
  • Input and output should be left to right in order of value, starting with the largest (i.e. 19 = XIX not IXX, 10 is larger than 9)
  • Left to right, no operator precedence, as if you were using a hand calculator.
  • Supports whole positive numbers input/output between 1-4999 (no need for V̅)
  • No libraries that do roman numeral conversion for you

For you to decide

  • Case sensitivity
  • Spaces or no spaces on input
  • What happens if you get a decimal output. Truncate, no answer, error, etc..
  • What to do for output that you can't handle. Negatives or numbers to large to be printed.

Extra Credit

  • -20 - Handle up to 99999 or larger (numbers with a vinculum)

Sample input/output

XIX + LXXX                 (19+80)
XCIX

XCIX + I / L * D + IV      (99+1/50*500+7)
MIV

The shortest code wins.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to be explicit about which variants of Roman numerals need to be supported. For example, do I have to understand IV as 4, or can I require that it be written as IIII? And what about, say, writing 8 as IIX instead of VIII, 19 as IXX or XVIV instead of XIX, or 99 as IC instead of XCIX? (All these variants have, AFAIK, been used classically.) \$\endgroup\$ – Ilmari Karonen Feb 9 '14 at 22:36
  • \$\begingroup\$ @IlmariKaronen thanks. I modified the question to be slightly more specific about that. \$\endgroup\$ – Danny Feb 10 '14 at 14:09
  • 1
    \$\begingroup\$ I think that using IV, IX, IC, XC, etc. should be alright, but only allow one prefix. Also, 19 should be written XIX, not IXX. One other thing, can we assume that the operators will be separated by a space, or no? \$\endgroup\$ – user10766 Feb 12 '14 at 0:32
  • 1
    \$\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 16:06
  • \$\begingroup\$ 1. I don't need to handle I/III but need to handle I/III+II/III? 2. For the extra can I output maybe [V] for 5000? \$\endgroup\$ – l4m2 Apr 12 '18 at 15:05
  • \$\begingroup\$ @programmer5000 it was posted to main awhile ago. codegolf.stackexchange.com/questions/20670/… \$\endgroup\$ – Danny Apr 26 '18 at 11:58
2
\$\begingroup\$

Golf a random Human Genome fragment with non-random features

A totally random genome fragment is easy enough: just spit out the letters ATCG in random order, and you're done. So let's try something a little less random and more useful to science.

Your program will:

  • Accept an argument from the user for number of base pairs (20bp-10000bp must be supported, more if you wish)
  • Accept an argument from the user for GC content. This indicates how frequently the generated sequence should contain the G and C bases as a percentage of total sequence length.
  • Include at least one complete gene in every request of 500bp or more, where a gene is defined as an otherwise random sequence that begins with a start codon triplet (ATG) and ends with the first stop codon triplet it encounters (TAG, TGA, or TAA). The distance between the start codon and the stop codon does not have to be a multiple of 3.
  • Vary gene content (the portion of the fragment that is "gene", inclusive of the gene's start and stop codons) linearly with respect to GC content (when sequence >= 500bp). At the extremes, when GC content is 0%, gene content is 10%; when GC content is 100%, gene content is 60%.
  • Output a single-strand sequence that complies with the above specs and the user's given parameters. (i.e. a single row of letters will suffice since it is trivial to deduce the complementary strand of the DNA given the sequence of one strand)
  • Calculate the actual GC content %, actual number of genes, and actual gene content % in the resulting fragment, and output a status line below the sequence conforming to the example format below. Percentages may be rounded to one decimal place. Actual values may deviate by +/- 3% from the expected outcome based on user's input.

    GC content: 42.1% | Genes: 3 | Gene content: 32.1%

Your program will not:

  • Use any Internet, library, or built-in gene sequence generation functions or databases. Roll your own.

Sufficient randomness:

  • For the purposes of this challenge, any built-in random/pseudo-random number generator function, GUID generator, well-seeded cryptographic hash function, etc. is considered an acceptable source of randomness.

What-ifs:

  • What if another start codon occurs before the stop codon? E.g. ATGXXXATGXXXXXXXXXXXXTAG. This is acceptable, but the "gene" length in this case is calculated from the most proximal start codon to the stop codon.
  • What if another stop codon occurs after a stop codon? E.g. ATGXXXXXXXXXXXXXTAGXXXXXXTAG This is also acceptable, but likewise the "gene" length is calculated from the start to the most proximal stop.
  • What if both of these things happen? E.g. ATGXXXATGXXXXXXXXXXXXTAGXXXTGA. Here again, the "most proximal" principle applies and the gene content is demarcated by the innermost start and the innermost stop.
  • Do "orphaned" start and stop codons that do not demarcate a gene count as gene content? No.

This challenge is code golf, so shortest valid code wins.

Post example output from a 500-bp request with GC content between 35% and 65%, and have fun!

| |
\$\endgroup\$
  • \$\begingroup\$ "Use hardcoded fragments for anything other than the start and stop codons." - why not? Specifying criteria for what counts as enough randomness should make these useless in any case. Speaking of which, you need to specify criteria for what counts as enough randomness. \$\endgroup\$ – John Dvorak Feb 28 '14 at 5:54
  • \$\begingroup\$ The only partial output example given flagrantly violates the spec. If the GC content is 42.1%, the gene content should be 31.05%, not 22.0%. The definition of "gene" is also imprecise: in the sequence AUGCCAUGCCUAGCUAA, which is the gene? \$\endgroup\$ – Peter Taylor Feb 28 '14 at 12:02
  • \$\begingroup\$ @PeterTaylor AUG starts the gene, then come the CCA, UGC, CUA and GCU triplets, none of which terminate the gene. Now if there were three C's instead of two, then UAA would be the terminating triplet and the whole sequence would form a gene. I agree the definition is imprecise, though. \$\endgroup\$ – John Dvorak Feb 28 '14 at 12:11
  • \$\begingroup\$ @JanDvorak, (part of) the point of that example is that there are two AUG substrings. \$\endgroup\$ – Peter Taylor Feb 28 '14 at 12:30
  • \$\begingroup\$ Good points. I was hoping to avoid having too much text, but that came at the expense of less clarity than the challenge demands. Edit forthcoming. \$\endgroup\$ – Jonathan Van Matre Feb 28 '14 at 13:58
  • \$\begingroup\$ Also, I've muddied the waters with RNA encoding and DNA encoding, (U vs T), which we can chalk up to a late night. \$\endgroup\$ – Jonathan Van Matre Feb 28 '14 at 14:00
  • \$\begingroup\$ Revised accordingly, although I remain open to suggestions on how best to frame the standards for acceptable randomness. I want something that won't be exploited by answers making no effort at randomness, but that doesn't have the pain-in-the-butt factor of generating 10mb+ of data and running a Diehard test battery. \$\endgroup\$ – Jonathan Van Matre Feb 28 '14 at 17:20
  • \$\begingroup\$ " This is acceptable, but the "gene" length in this case is calculated from the most proximal start codon to the stop codon. " - wait, what? In nature, the first one is the start codon, and the rest encode methionine. Under your scheme, methionine (which is an essential amino-acid) would be impossible to include into proteins. Your scheme would also be much harder to splice. Also, what happens to AUG substrings that are not triplet-aligned to previous AUG substrings? \$\endgroup\$ – John Dvorak Mar 1 '14 at 9:25
  • \$\begingroup\$ In nature, the first ATG encodes the start of a protein coding region and defines a reading frame (triplet boundary), the rest encode methionine and the first triplet aligned stop codon encodes the end of the protein coding region (and no amino-acid). \$\endgroup\$ – John Dvorak Mar 1 '14 at 9:29
  • \$\begingroup\$ As for the randomness, I'm not worried about the source of randomness (whatever native library is available is assumed to be good enough) but rather how the source of randomness is used (can we just start the sequence with a start codon and insert an end codon at just the right spot if it doesn't occur naturally sooner, then fill in with more random codons while avoiding ATG subsequences? Your "sufficient randomness" places constraints on the RNG (useless) but no constraints on how it's used (or that it needs to be used at all) \$\endgroup\$ – John Dvorak Mar 1 '14 at 9:34
  • \$\begingroup\$ My true random number sequence generator was sitting there watching silently as I typed away the sequence ACACACACACACAC.... It's all okay. The TRNG was capable of producing something better - it just didn't really get to it. \$\endgroup\$ – John Dvorak Mar 1 '14 at 9:38
  • 1
    \$\begingroup\$ In fact, the 3% tolerance for the CG content leaves no room for randomness when there are only 20 base pairs. I can shuffle the pairs and turn some A<->T or C<->G, but that's it. In fact, if the CG content is set to zero, the task is impossible: we want a gene content of 2 base pairs (which is itself impossible), but the start codon contains a G, and a single G in a 2bp sequence means a 5% CG content, 2% than is the limit. Not including a gene means that we are 7% under the gene content lower limit. Similarly, it's not possible to start or stop a gene with nothing but Cs and Gs. \$\endgroup\$ – John Dvorak Mar 1 '14 at 9:45
  • \$\begingroup\$ Yeah, the 20bp starting point is a bad idea. The problem with start codons is that I considered introducing the idea of promoters and decided that would make the whole thing too complex. So in the absence of promoters there has to be some way to determine which Met is the start codon vs an amino acid and the easiest simplification is to have no Mets in the gene. Likewise, for "not triplet aligned", I'm trying to avoid having to go into explanations of frameshift mutations (even though a Frameshift% would be a cool parameter). \$\endgroup\$ – Jonathan Van Matre Mar 1 '14 at 14:29
  • 1
    \$\begingroup\$ I am starting to think that all of these complexities should be included (this proposal stems from me noticing that most of the extant random DNA generators are pretty weak) and this should just be a popularity contest instead of a golf. Link a couple of good articles on the structure of the genetic code and let people add as many features as they wish. Making it a golf seems to be a catch-22 between too many compromises or a too-impenetrable wall of rules and conditions that will dissuade participation. \$\endgroup\$ – Jonathan Van Matre Mar 1 '14 at 14:33
  • \$\begingroup\$ Perhaps a code-challenge where people earn x points for each complexity implemented? \$\endgroup\$ – user10766 Mar 2 '14 at 5:52
2
\$\begingroup\$

DIM, the DIM Integer Machine

The DIM Integer Machine is an engine for producing integer sequences.

It has one major problem: To put it mildly, it's kind of...dim.

After producing a single number, it immediately forgets what sequence it was working on. The only thing it remembers is the last number it produced and the current direction of the search, either ascending or descending. (And of course, it remembers the methodology for finding numbers according to the commands it understands).

Consequently, the user is free to change their mind after each number by issuing a new command.

Suppose the DIM has just produced an integer square: 81

  • User inputs P and submits the input.
  • DIM understands that P is requesting the next prime number after 81
  • DIM computes and returns 83.
  • DIM forgets what it was doing.
  • User inputs O.
  • DIM understands that O is requesting the next odious number and returns 84.
  • DIM forgets what it was doing.

The DIM functions only for numbers between 1 and 1,000,000. If the DIM reaches either extreme while performing a search it will reverse direction and continue searching.

(For example: If searching in ascending order for a prime when the last number was 999,999, it will encounter 1,000,000 which is not a prime, then switch to descending order and continue searching for the "next" prime by moving downward - 999,999...999,998, etc.)

The DIM remembers the last number as 1 when it is first activated for a searching session.

This is the full list of commands that the DIM understands:

  • P - Next prime number
  • S - Next square number
  • F - Next Fibonacci number
  • O - Next odious number
  • W - Next wasteful number
  • U - Next undulating number
  • K - Next katadrome
  • R - Reverse direction immediately; the next command will proceed in the new direction

Because the DIM is so...dim, it absolutely DOES NOT precompute lookup tables of numbers in these sequences. It is far too forgetful for that to work. The DIM also has no Internet connection, so it is unable to consult the Online Encyclopedia of Integer Sequences or other such sites. It also has a sense of pride, so it does not make use of built-in Fibonacci functions or NextPrime / PrimeIndex / PrimeTest type functions.

Given the parameters it knows - a starting number, a search direction, the type of number to find - it simply computes the next number by some means other than mere data retrieval.

The DIM may accept input interactively, or from a newline-terminated text file, or from a pre-initialized array. You may not pack extraneous data other than the command sequence into the input - play fair!

This is a code golf, so least number of bytes wins. Submit your program with output results for the following search sessions:

  1. P O U R F O R U S O U R P R O W S
  2. W O R K F O R P O O R F O R K S K O O P S R O O K S F O U R W O W S
  3. P O O P O O P O O P P O O P P R O P S P R O W S P O R K S

It is assumed that you know what prime, square, and Fibonacci numbers are. A brief explanation of the other integer sequences follows.

Odious - a nonnegative number which has an odd number of 1s in its binary expansion. The first few odious numbers are 1, 2, 4, 7, 8, 11, 13, 14, 16, 19

Wasteful - a natural number that has fewer digits than the number of digits in its prime factorization (including the exponents). The first few are 4, 6, 8, 9, 12, 18, 20, 22

Undulating - has alternating digits of the form aba, abab, ababa, etc. Assume all U numbers are non-trivial, i.e. 3 digits or more. The first few: 101, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212

Katadrome - A number whose hexadecimal digits are in strict descending order. The first few are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32, 33, 48, 49

| |
\$\endgroup\$
  • \$\begingroup\$ When I post the question, I'll also include external links to MathWorld or OEIS for those who need more detail on the less familiar sequences, but the explanations above should be sufficient for most, I think. \$\endgroup\$ – Jonathan Van Matre Mar 6 '14 at 23:28
  • \$\begingroup\$ Your definition of "undulating" isn't the one I'm familiar with, which just requires that the digits alternately increase and decrease. Also, it would be better to include expected answers for the test cases, so that submitters can use them as test cases rather than them serving just for you to say "No, this is buggy". \$\endgroup\$ – Peter Taylor Mar 6 '14 at 23:57
  • \$\begingroup\$ Yes, that's my plan, I just haven't finished double checking my results for the test cases yet. OEIS and Mathworld have the strict 2-digit definition of undulating, but I'll make sure to make the definition here more prominent so it is clear which interpretation is meant. \$\endgroup\$ – Jonathan Van Matre Mar 7 '14 at 0:04
  • \$\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 16:09
2
\$\begingroup\$

Unified format patcher

Write the shortest program that will take a patch file in the unified format from stdin and apply that patch. No external tools that do the process for you can be used.

Clarifications

  • Extra documentation about the unified format can be found here
  • All file paths will be relative
  • Only one file will be modified per patch
  • Timestamps can be ignored
  • The patch file will be valid and will apply cleanly to the file specified (it will not lie about line numbers, etc..)
  • Assume all files being patched already exist, you don't need to create/delete files

Extra

  • -35 - Take an argument that allows you to unpatch a patch

Example

/test/a.cpp

#include <iostream>
using namespace std;

int main() {
    cout << "Hello world!";
    return 0;
}

patch.txt

--- a/test/a.cpp
+++ b/test/a.cpp
@@ -1,7 +1,8 @@
 #include <iostream>
+#include <vector>
 using namespace std;

 int main() {
-    cout << "Hello world!";
+    cout << "Goodbye world!";
     return 0;
 }

Run patch

patch.exe patch.txt

/test/a.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cout << "Goodbye world!";
    return 0;
}
| |
\$\endgroup\$
  • \$\begingroup\$ Can the program assume that the @@ lines contain the correct line numbers? \$\endgroup\$ – ugoren Mar 6 '14 at 17:52
  • \$\begingroup\$ A good explanation of the patch file format is needed. If not too long, include it in the question. Else, provide a link. \$\endgroup\$ – ugoren Mar 6 '14 at 17:53
  • \$\begingroup\$ You forgot the obvious "no external tools" disclaimer. You don't want the patch $1 answer. \$\endgroup\$ – ugoren Mar 6 '14 at 17:55
  • \$\begingroup\$ @ugoren thanks for the comments, I added some further clarifications. \$\endgroup\$ – Danny Mar 6 '14 at 18:38
  • \$\begingroup\$ Does "The patch file will be valid (it will not lie about line numbers)" also mean that it will apply cleanly? \$\endgroup\$ – Peter Taylor Mar 6 '14 at 19:24
  • \$\begingroup\$ @PeterTaylor yes, updated question. \$\endgroup\$ – Danny Mar 6 '14 at 19:51
  • \$\begingroup\$ "The shorted program" should say "the shortest program", but other than that I think it's ready to go. Of course, no-one's actually going to do more than filter out the lines starting -, remove the first char from each line, and parse the line-numbers to work out how to splice the resulting text in. \$\endgroup\$ – Peter Taylor Mar 7 '14 at 0:01
  • \$\begingroup\$ This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:10
2
\$\begingroup\$

Efficient Testing for Armstrong Numbers

An Armstrong Number (also known by different names, including Narcissistic Number; see Wikipedia for more information) is a non-negative number (for our purposes represented in base 10) that is equal to the sum of the individual digits of the number each raised to the power of the number of digits. For example:

  1. Start with the three digit number 407.
  2. The individual digits are 4, 0, & 7.
  3. Since it is a three digit number, we raise each digit to the third power: 64 (4^3), 0 (0^3), & 343 (7^3).
  4. The sum of those values is 407 (64 + 0 + 343).
  5. Because the final sum is equal to the original number, it is an Armstrong Number.

By contrast:

  1. Start with 47.
  2. The individual digits are 4 & 7.
  3. A two digit number, so raise each digit to the second power: 16 (4^2) & 49 (7^2).
  4. The sum of those values is 65 (16 + 49).
  5. The final sum of 65 is not the original number, so it is not an Armstrong Number.

Your mission, should you decide to accept it: Write a program in any programming language (using only standard language features and libraries) implementing the most efficient algorithm possible to test the numbers from 1 through 18,446,744,073,709,551,615 (264-1) inclusive for "Armstrongness", generating a list of Armstrong Numbers, and only Armstrong Numbers, as output.

While any language is acceptable, it should be obvious that interpreted scripting languages will be at a disadvantage in the efficiency department. That being said, a superior algorithm in an interpreted scripting language can beat the pants off an inefficient algorithm in hand tuned assembly language.

Winning Criteria

The algorithm that can check all possible candidate numbers for "Armstrongness" in the least amount of time on a reference computer will be the winner. The reference computer will have the following specifications: {approximately an AMD Phenom class computer with 8 GB RAM running Windows 7 Ultimate 64 bit}

| |
\$\endgroup\$
  • \$\begingroup\$ I don't know that this would belong in the (already very long, maybe too long) problem statement above, but other historical background. The class was for Fortran 77, and I was in a friendly competition with my TA to write the shortest version. I never could win that one, so I decided to write the most efficient version instead. Hence: I prefer efficiency puzzles to code golf (though code golf is fun too). \$\endgroup\$ – CasaDeRobison Feb 20 '14 at 8:30
  • 1
    \$\begingroup\$ This doesn't seem to have an objective winning criterion. You do list "criteria I'll be using to judge this", but a) it mixes specification with winning criteria; b) it combines factors without indicating their weight. \$\endgroup\$ – Peter Taylor Feb 20 '14 at 11:51
  • \$\begingroup\$ The question also seems to be about twice as long as it needs to be. If you use the [link text](url) link notation you can shorten it slightly; you can also lose paragraphs by cutting the worked example and brute-force code (link to the existing question on narcissistic numbers instead); cutting the waffling about which languages you think have advantages; and simplifying the motivation. \$\endgroup\$ – Peter Taylor Feb 20 '14 at 11:57
  • \$\begingroup\$ I think efficiency problems are not well suited to code-golf. The efficiency of an algorithm depends on too many factors. You could perhaps require the lowest number of power operations. \$\endgroup\$ – ugoren Feb 20 '14 at 12:43
  • \$\begingroup\$ @ugoren, 0 is easily obtained. \$\endgroup\$ – Peter Taylor Feb 20 '14 at 12:57
  • \$\begingroup\$ @PeterTaylor, You're right. Still, trying to replace a time measurement with the number of operations of a certain type sometimes helps define the problem better. \$\endgroup\$ – ugoren Feb 20 '14 at 15:12
  • \$\begingroup\$ @PeterTaylor: I agree it is quite long, and will consider revisions to it. \$\endgroup\$ – CasaDeRobison Feb 20 '14 at 21:43
  • \$\begingroup\$ @PeterTaylor: I'm open to better phrasing of the "objective winning criteria" but really, it is pretty objective already. One, no wrong answers allowed in the winner. Two, how efficient is the algorithm (based on the range of numbers tested and time taken to test them). For example, an algorithm that tests all numbers through 9 digits in 100 seconds is faster than an algorithm that takes 20 seconds to test all numbers through 8 digits (10 times larger interval in only 5 times the time). How might you suggest integration of this with the problem statement? \$\endgroup\$ – CasaDeRobison Feb 20 '14 at 21:48
  • \$\begingroup\$ @PeterTaylor: Glad I included the disclaimer about failing eyesight, given that I searched for narcissistic numbers and came up with nothing. I either searched the wrong portion of PCG (meta) or I made a typo when spelling narcissistic. \$\endgroup\$ – CasaDeRobison Feb 20 '14 at 21:49
  • \$\begingroup\$ @ugoren: efficiency may not be suited to code golf, but my understanding was that this 'forum' was about "programming puzzles" and "code golf". I certainly would consider finding a more efficient algorithm to be like solving a puzzle, though maybe I'm alone in that, in which case no biggie. \$\endgroup\$ – CasaDeRobison Feb 20 '14 at 21:51
  • \$\begingroup\$ Edited the problem statement (which is still admittedly quite long, still considering other edits) by removing the final PPS paragraph and replacing the existing links as suggested. \$\endgroup\$ – CasaDeRobison Feb 20 '14 at 21:59
  • 1
    \$\begingroup\$ The winning criterion is still too imprecise IMO. (NB Of the judging criteria you list, the first is part of the spec, so it's an acceptability criterion rather than a winning criterion). A genuinely objective winning criterion allows me to calculate my score before I submit my answer. \$\endgroup\$ – Peter Taylor Mar 12 '14 at 8:47
  • 1
    \$\begingroup\$ It should be much shorter in order to not discourage people from approaching your challenge. Almost all the text after the definition doesn't add anything to the challenge - beside "don't print wrong numbers" which is of course relevant. I also think that a more precise criterion should be given instead. \$\endgroup\$ – Howard Mar 12 '14 at 9:03
  • \$\begingroup\$ I've posted a "radical" update to it. I suspect the new winning criteria will not be acceptable either, since it involves a "reference computer" for final timing. Very open to suggestions on how to restate it so that a crappy algorithm on fast hardware doesn't beat an efficient algorithm on slow hardware. \$\endgroup\$ – CasaDeRobison Mar 12 '14 at 20:17
  • \$\begingroup\$ The possibility that processor architecture or available memory affects the results is a tricky issue with fastest-code questions, but there isn't really a better way of comparing speed of programs than measuring on a large test case. I can at least measure how my program compares to someone else's on my computer, and know whether it's close or not. \$\endgroup\$ – Peter Taylor Mar 12 '14 at 21:23
2
\$\begingroup\$

Amino Acids Matcher

In genetics, a codon is a set of three nucleotides, the most basic form of nucleic acids. A codon "codes" (no pun intended, that's the actual term used) for a specific amino acid. Given a string of DNA, it is converted into RNA form by taking the opposite complementary pair.

DNA    RNA
A      U (T changes to U)
T      A
C      G
G      C

You will be given a String of unknown length that contains multiple codons. You must convert them to RNA form and print out the amino acid for each. See here for a chart: http://en.wikipedia.org/wiki/RNA_codon_table#RNA_codon_table


Sample Input

TACTCGGATACT

Is split into

TAC, TCG, GAT, ACT

We now change each letter to its reciprocal

AUG, AGC, CUA, UGA

And print out the amino acids

Methionine, Serine, Leucine, Stop


This would probably be

I know that this is most likely not sufficiently explained and might be too complicated. Additional, tell me if there is any incorrect information above.

| |
\$\endgroup\$
  • \$\begingroup\$ So basically this is a challenge to compress a lookup table. You should probably specify that the string will be a multiple of three characters (or specify what to do otherwise); and it would seem sensible to inline the lookup table so that a) the question doesn't rely on the external page remaining intact; b) you save everyone who wants to answer the question the hassle of calculating it. \$\endgroup\$ – Peter Taylor Mar 17 '14 at 12:42
  • \$\begingroup\$ Thanks for the feedback. I'll update accordingly later today. \$\endgroup\$ – nrubin29 Mar 17 '14 at 15:48
2
\$\begingroup\$

Find words in word square solver

On social media I often see images with letters and in them are some positive words for people to find. I challenge you to write a program that finds all words in the puzzle that matches a input dictionary. An example of such puzzle is this one:

A letter square

An ASCII representation I made of this:

XCUALOVEYKBWSNG
DUAWKCBEAUTYRJV
YOUTHFSMGNEZLPR
MHJREYWDKZLUSTJ
FSUCCESSDHEALTH
ENMQXPTIMELMSAQ
VEXPERIENCEGHBW
GHUMOURLOYMONEY
SYZPOPULARITYNA
AMKCFUNBXHUZYIX
CWIHYSHAPPINESS
HONESTYCFRIENDS
KPYJAETWPOWERQC
BTYACFREEDOMJMO
RIWINTELLIGENCE

Now I imagine we can find words horizontally, vertical and diagonal and all of the mentioned in reverse. The program must be able to take a square and a dictionary like this one and print all the matching words.

As a test case I give custom dictionary:

bar
bid
dir
dog
fad
fed
foo
god
man
mod
set
sun

And a test square:

OGFIR
DOMAN
ODBID
OPGES
OGFIR

Your code should be able to print all but the two last words in the dictionary. For diversity you should specify how the cube and the dictionary is bo be entered.

This is so shortest code wins.

| |
\$\endgroup\$
  • \$\begingroup\$ What should be output? Only the matched words? Their positions? And directions? \$\endgroup\$ – John Dvorak Apr 3 '14 at 15:47
  • \$\begingroup\$ @JanDvorak Just print the words found. Do you think coordinates and direction can be given a bonus? \$\endgroup\$ – Sylwester Apr 3 '14 at 15:51
  • 3
    \$\begingroup\$ Cube? I'm only seeing two dimensions. On a more general note, perhaps for questions of this sort it would be OK to assume the availability of a standard dictionary file like /usr/share/dict, and discount the characters used to access this file? What do people think? \$\endgroup\$ – r3mainer Apr 3 '14 at 15:55
  • \$\begingroup\$ @squeamishossifrage OMG You're right. I meant square of course :-) I think people can choose. eg. The question is open for diversity like cat square.txt dic.txt | solver now, but I'm open for change that does not discriminate. \$\endgroup\$ – Sylwester Apr 3 '14 at 16:03
  • 1
    \$\begingroup\$ How does the program know where the wordsearch ends and the dictionary starts? \$\endgroup\$ – Peter Taylor Apr 3 '14 at 21:39
  • \$\begingroup\$ @PeterTaylor By mistake I made the test a rectagle, but I fixed that. The length of the first line would be the number of lines in the square. Anyway how the input is done I thought should be up to the solver so that they can choose to open files, read stdin or maybe more disturebing ways to get input in... \$\endgroup\$ – Sylwester Apr 3 '14 at 21:47
  • \$\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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:30
  • \$\begingroup\$ @programmer5000 It only got two upvotes so I let it be. Feel free to post it if you'd like. \$\endgroup\$ – Sylwester Jun 12 '17 at 15:27
2
\$\begingroup\$

Collatz ...something

The Collatz conjecture states that every natural number n leads to the number 1 if the recursive function f(n) is applied to it defined as

f(n)=n/2    if n is even
    =3n+1   if n is odd

Let "ai" be the value of f applied to n recursively i times so that a0 = n , a1 = f(n) , a2 = f(f(n)) ... ai = f(ai-1)

Let A be the set {a0, a1, ..., 1}

Thus, for n=10, we get the sequence

a0 = 10 --> a1 = 5 --> a2 = 16 --> a3 = 8 --> a4 = 4 --> a5 = 2 --> a6 = 1

and the set A as A = {10,5,16,8,4,2,1}

Your task is to write a function/program that will accept a set of naturals say I. You must output a set of numbers say C such that I is a subset of the union of the sets A for all numbers in C.

Rules

  • Network access is forbidden
  • Any of the standard loopholes are forbidden
  • Your program must end in less than 200 seconds. You may assume that all the input terms are less than 2^(45); however note that the individual terms of the collatz sequence can go higher.

Input

  • List/array of naturals in I as an argument to a function
  • , or space or \n separated naturals in I on STDIN

Output

  • return a list/array/set of all naturals in C
  • print all the naturals in C separated by \n

Scoring

Your score is calculated as

( ( (10)^(number of elements in C) ) * (sum of all elements in C) ) + ceil( 100*log(total number of bytes of your code) )

log() is the natural logarithm

Lowest score wins.

Examples

Input:

I = { 16 , 32 , 40 }

Possible outputs along with the score

C=                   Score

{ 16 , 32 , 40 }     ((10)^(3))*(16 + 32 + 40) = 8000   + constant
{ 32 , 40 }          ((10)^(2))*(32 + 40)      = 7200   + constant
{ 32 , 13 }          ((10)^(2))*(32 + 13)      = 4500   + constant --> most optimal         
{ 1024 , 320 }       ((10)^(2))*(1024 + 320)   = 134400 + constant
... Infinitely many higher numbers    

where constant is ceil(100*log(code length))

In this case, the answer { 32 , 13 } is the most optimal.


Note: This is NOT code-golf even though the length of your program is considered. Please also provide a readable version.

I'm being flexible with the I/O so that the more verbose languages might get some benefit. You can write a complete program or a function or a lambda function. It is not required that your function(if you choose to write one) returns. Using a function for input while printing the output is fine if that makes the code shorter.


This will be tagged as


Sandbox feedback

  • Can anyone suggest a better title?

TODO

  • Scoring needs specific test cases. Perhaps the final score could be the average of all scores of the test cases.

  • Needs a proper title.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ The timing constraint is not reasonable unless you also provide constraints on the number and size of the inputs. For any input for which the constraint is reasonable at all, I think that the first point of the spec is unnecessary: if a counterexample exists, it's right at the edge of what fits in a 64-bit number. The second point of the spec is currently quite difficult to understand. \$\endgroup\$ – Peter Taylor Apr 3 '14 at 9:47
  • \$\begingroup\$ @PeterTaylor Is it OK now? \$\endgroup\$ – user80551 Apr 4 '14 at 16:15
  • 2
    \$\begingroup\$ Looking around a bit at the standard terminology, I think that it might be best introduced with something like "Each positive integer n generates a Collatz sequence by repetition of the map f(n) = n % 2 == 0 ? n/2 : 3*n+1. Define the orbit of n as the set containing the integers in its Collatz sequence, and the orbit of a set {n_i} as the union of the individual elements' orbits. Your task is to find an optimal set under the constraint that its orbit contain a specified subset." That then leads into the example. \$\endgroup\$ – Peter Taylor Apr 4 '14 at 16:48
  • 2
    \$\begingroup\$ I'm not sure that it's justifiable to claim that for your example {I2, C5, C10} is "(not the most ideal)". Whether or not it is depends on which arrows are /2 and which are *3+1, which isn't shown in the example. It's also occurred to me, which I missed earlier, that your scoring system requires a bit more of a test suite: at present, you have no way of distinguishing between answers which get the optimal solution to one test case. And I suggest a title, based on my previous comment: "Optimal Collatz orbits". \$\endgroup\$ – Peter Taylor Apr 4 '14 at 16:52
  • 1
    \$\begingroup\$ I suggest you to add a link describing what is a collatz sequence. As a non-mathematician, I find it hard to understand. There is extra whitespaces after `` in your first code block. \$\endgroup\$ – A.L Apr 4 '14 at 17:12
  • \$\begingroup\$ @PeterTaylor Edited a lot. Are you sure it is called an orbit? I couldn't find that term anywhere. \$\endgroup\$ – user80551 Apr 6 '14 at 16:39
  • 1
    \$\begingroup\$ It occurs 4 times in the Wikipedia page on the Collatz conjecture, and Google gives over 6 million hits for collatz orbit. \$\endgroup\$ – Peter Taylor Apr 6 '14 at 22:08
  • \$\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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:31
2
\$\begingroup\$

Filter out repetitive lines

Google Suggest doesn't show any results if a string contains more than 4 repetitions of a substring. More specifically, if a substring is repeated 4 times in a row, followed by the first character of that substring (i.e. abcabcabcabca or x x x x x), nothing is suggested. This rule changes slightly if the substring is all the same digit - a digit may be repeated 5 times in a row, but no more. This is probably to allow searching for ZIP codes like 22222. (This doesn't extend to strings like 1010101010, though.)

Let's simulate this behavior! Write a program that takes lines on standard input and echoes those lines back on standard output, unless the line fits the criteria for repetitiveness, in which case it's silently discarded.

Sample input:

a simple query
nananananananana
ffffgggghhhh
48719999936
abc abc abc abc asdf
xyzzzzzyx
122333444455555666666
repetitiverepetitiverepetitiverepetitive
erepetitiverepetitiverepetitiverepetitive
101010101
55555 zzzzz

Output:

a simple query
ffffgggghhhh
48719999936
repetitiverepetitiverepetitiverepetitive

(Google's behavior is actually quite a bit more complicated than this; there are a few exceptions to all of these rules, but let's just ignore those for this challenge.)


There was a similar challenge posted awhile ago (Recognizing Repetition in strings), but it was closed due to vagueness. I think the criteria proposed above are more than thorough enough.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ The current exceptions make it complicated enough to track what you're looking for: basically you're asking for grep -v ((.).+)\2{3}\1|([^0-9])\3{4}? \$\endgroup\$ – Peter Taylor Apr 19 '14 at 19:05
  • \$\begingroup\$ @PeterTaylor I would like to try to solve it without regex, though. \$\endgroup\$ – John Dvorak Apr 19 '14 at 19:10
  • \$\begingroup\$ I had thought about regex, but I didn't think it would be that simple. Would adding more restrictions or banning regex help? \$\endgroup\$ – Fraxtil Apr 20 '14 at 1:18
  • \$\begingroup\$ @Fraxtil, my opinion is that as a general rule if you need to ban the obvious way of doing something then you might as well just abandon the question. (With the exception, obviously, of banning libraries which are specifically designed to solve the same problem. Regex being a general tool rather than something designed for this specific problem don't fall into that exception). \$\endgroup\$ – Peter Taylor Apr 21 '14 at 8:52
  • \$\begingroup\$ @PeterTaylor, that's a good point. Maybe I'll revisit the idea later if I can find a way to make it more interesting. \$\endgroup\$ – Fraxtil Apr 21 '14 at 18:56
  • \$\begingroup\$ I did make a decent question out of doing a basic regex problem without the use of regex (I should have, in hind sight, banned basic pattern matching as well as regexes...Bash shouldn't almost beat APL in sheer character count in a code golf). \$\endgroup\$ – Isiah Meadows Apr 21 '14 at 21:06
  • \$\begingroup\$ @impinball "Bash shouldn't almost beat APL in sheer character count in a code golf" -- why? \$\endgroup\$ – John Dvorak Apr 24 '14 at 12:53
  • \$\begingroup\$ Or at least in that context (tr is a pattern matching replace algorithm with regex like functionality). I would be a little more likely to accept Bash's builtin pattern matching expansion than tr. \$\endgroup\$ – Isiah Meadows Apr 25 '14 at 21:49
2
\$\begingroup\$

Am I a Matroid?

Input:

A list I that is a subset of the powerset of E={1,2,...,n} which represents the independent sets of elements of the purported matroid M=(E,I). Note that the cardinality of the ground set may be for the purposes of this question ignored. Any elements of E that appear in none of the elements of I cannot contribute (i.e. if M=(E,I) is a matroid then M=(E union K,I) is a matroid for any set K.

Input may be in whatever list format you desire, be it as simple as no separators but spaces (using 0 for the empty set): 0 1 2 3 12 13 or as complicated as whatever list literals are in your favorite language (such as python's: [[],[1],[2],[3],[1,2],[1,3]]).

Output:

A variation on 1/0, true/false, yes/no answering the question: is M a matroid?

Definition:

M=(E,I) is a matroid if:

  1. I is not the empty set
  2. If J is in I and K is a subset of J, then K is in I
  3. If J,K are in I and |K|<|J| then there exists an element x that is in the set difference J-K such that K union {x} is in I.

There are equivalent formulations of condition 1 and 3, also there are conditions on the bases (maximal elements of I w.r.t. cardinality) that are equivalent to these. If people want I can post those too or leave them as optional research.

Examples:

I={{},{1},{2},{1,2}} is a matroid.

I={} is not a matroid because it is empty (by axiom 1).

I={{},{1},{1,3}} is not a matroid because if it has {1,3} independent then it must have {3} independent (by axiom 2).

I={{},{1},{2},{3},{1,2}} is not a matroid because if it has {1,2} and {3} independent then it must have either {1,3} or {2,3} independent (by axiom 3).

I={{}} is always a matroid, as is I=powerset([1,2,...,n]) for any n>0 as they both trivially satisfy the axioms.

Specs:

Submission is either a program taking input from standard input or command line argument or a function that takes I as input (as a string) and returns the specified binary answer. No upperbound on the size of input should be hardcoded.

I would intend for this to be a code-golf challenge.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ Rather than provide alternative definitions, just link the first mention of the word matroid to the Wikipedia page. \$\endgroup\$ – Peter Taylor May 5 '14 at 11:59
  • \$\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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:38
2
\$\begingroup\$

Type me out.

Your task (related to this question) is to translate any text (in a file, or simply input) into the input of a telephone keypad.

enter image description here

and provide a keypress score.

As the keypad has a limited set of keys you have to 'encode' your non-alphanumerics with their ASCii hexadecimal encoding; e.g. to type ~ you press the hash key once, the 7 key (once to get a seven) and then 3 three times to cycle through the digits 3, 'd', and finally 'e'. This gives the code #7e which corresponds to ~. Spaces and capitals have to be accessed via hex code (so MY_CONST (#4d #59 #53def #43 #4f #4e #53 #54 - 27 presses) costs you less than my_const (6m 9wxy #53def 2bc 6mno 6mn 7pqrs 8t - 29), but more than myconst (6m 9wxy 2bc 6mno 6mn 7pqrs 8t - 23)).

For instance If your code had print() that would cost 15 for the print (7p 7pqr 4ghi 6mn 8t) plus 6 for the () (#28 #29)

To be clear with just the input print() the output is:

7p 7pqr 4ghi 6mn 8t #28 #29
21

(Note however the hex codes for c f i r s v y z are shorter (correspondingly #63 #66 #69 #72 #73 #76 #79 #7a) than long hand key presses. It's perfectly allowed to score print() as 19:

7p #72 #69 6mn 8t #28 #29
19

)

This is Code Golf, so feed your code into the finished program - shortest answer wins.

| |
\$\endgroup\$
  • \$\begingroup\$ @m.buettner typically when typing on a phone keypad you have to press the number first, and each subsequent press is a letter and then it cycles round. Spaces have to be hex values, capitals require hex codes as well. Scoring is as you state. \$\endgroup\$ – Pureferret Jul 9 '14 at 11:42
  • \$\begingroup\$ @m.buettner I added them as soon as I had finished replying to your comment. Is it clear enough now. And yes you can use those short cuts instead of typing them long. I'll add that in a second. \$\endgroup\$ – Pureferret Jul 9 '14 at 12:05
  • \$\begingroup\$ Better! :) ... I think myconst should be 24 though. And your output for that is somewhat different from your example output later one. Where you show the counting you only write the resulting letter whereas in the actual example output you show the sequence. Which also raises the question whether letters in hex codes should be expanded in the actual output (which would be necessary for correct counting). \$\endgroup\$ – Martin Ender Jul 9 '14 at 12:11
  • \$\begingroup\$ @m.buettner I'm not very good at this challenge, that's why I need people to so it for me! I'll update the score now, and clarify the output as well. \$\endgroup\$ – Pureferret Jul 9 '14 at 12:40
  • \$\begingroup\$ @m.buettner How is it now? Ready? \$\endgroup\$ – Pureferret Jul 10 '14 at 9:21
  • \$\begingroup\$ I think so, but you should wait for two other people to tell you that. \$\endgroup\$ – Martin Ender Jul 10 '14 at 9:32
2
\$\begingroup\$

The Painter's Predicament

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

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

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

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

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


Input

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

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

Examples: ABCDEF, ZZZZZZ, and AAAAAC.

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

Examples: 3 ABC, 10 QRSTUVFGHJ

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


Output

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


Additional Details

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

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

n is at least 3.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ does the machine have to start with its color set to A? does it have to start off pointed at wall 0? \$\endgroup\$ – Sparr Aug 5 '14 at 23:57
  • \$\begingroup\$ Good catches, yes, and yes. I'll edit it in. \$\endgroup\$ – Mike Precup Aug 5 '14 at 23:58
  • \$\begingroup\$ If a 3 is passed in, is the house a triangular prism? \$\endgroup\$ – Nathan Merrill Aug 6 '14 at 18:06
  • \$\begingroup\$ Yep. I suppose I should lower bound n, since it doesn't make much physical sense to have n < 2. \$\endgroup\$ – Mike Precup Aug 6 '14 at 18:09
  • 2
    \$\begingroup\$ Some test cases would be good. \$\endgroup\$ – Peter Taylor Aug 7 '14 at 22:14
  • \$\begingroup\$ This looks to be a Travelling Salesman problem on the rectangle grid graph (with one dimension looped around). It's open whether it's NP hard (cs.smith.edu/~orourke/TOPP/P54.html), which means no polynomial-time algorithm is know. This mean optimal solutions probably take very long to find. Is there a time limit? \$\endgroup\$ – xnor Sep 25 '14 at 19:04
  • \$\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.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:56
2
\$\begingroup\$

Figure significant figures

Your challenge is to write a program that finds how many significant figures a given number has.

Rules for finding significance

  • All numbers 1–9 inclusive are significant.
  • All leading zeroes are not significant.
  • Trailing zeroes are significant only if there is a decimal point present anywhere.
  • Zeroes surrounded on both sides by nonzero digits are significant.

Input/output

  • Input from STDIN or similar.
  • Input will be one string.
  • The input can be arbitrarily large floating-point numbers, but no larger than your language can handle. [I'm not sure if this is the right term/makes sense]
  • If the input contains anything other than digits 0–9 or ., or is too large to compute, output Invalid.
  • The output will be one string to STDOUT or similar.

Further information

  • Using an external source such as a website, as well as any libraries, APIs, functions, or the like that calculate significant figures are not allowed.
  • Loopholes that are forbidden by default are not allowed.
  • This is , so fewest byte wins.

Test cases

Input    Output
---------------
7        1
7.0      2
07       1
0.07     1
70       1
70.      2
70.0     3
9000     1
9001     4
.000001  1

I'd appreciate any feedback, questions, or comments.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ Why the bit about floating point numbers? Anyone who doesn't process the string directly is highly likely to have bugs due to the impossibility of exactly representing powers of 0.1 in binary. \$\endgroup\$ – Peter Taylor Aug 27 '14 at 6:55
  • \$\begingroup\$ @PeterTaylor I don't understand floating point numbers too well, so I may have used the wrong term. I meant to refer to any number with a decimal point (like 23.391). \$\endgroup\$ – NinjaBearMonkey Aug 27 '14 at 11:56
  • \$\begingroup\$ I think you used the correct term: my point is that floating point support should be irrelevant. This is an easy task even for languages like BF which don't have any data types except integers. If you want to place bounds on the size of the input, I would bound it at 255 characters and include a 255-character test case. \$\endgroup\$ – Peter Taylor Aug 27 '14 at 13:12
  • \$\begingroup\$ I like this challenge idea. Regarding the "arbitrarily large floating point numbers" bit, maybe it would be better to restrict input to valid cases so you don't have to worry about passing in too large (2^100) or too small (2^-100) numbers. \$\endgroup\$ – El'endia Starman Nov 13 '15 at 7:14
  • \$\begingroup\$ @programmer5000 Sure, feel free to adopt it. (Note that I never really resolved the issues discussed in the comments, though.) \$\endgroup\$ – NinjaBearMonkey Jun 11 '17 at 17:03
2
\$\begingroup\$

Old fashioned intelligence gathering

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

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

DQSIRINKSFIJATOAPQFFOUSJAR

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

QSIFIJOAPQFSJA

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

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

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

Rules

Input

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

Output

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

Other notes

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

Scoring:

  • Code golf, shortest code wins.

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

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

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

ASOIIJHAWQRATEMSDQPOYJKWEOABS (ink tape)
ASOIJWQRASDQPOKWEAS (correction tape)
I HATE MY JOB (decoded message)
| |
\$\endgroup\$
  • \$\begingroup\$ So I get a -25 bonus just for adding "HELOVESNAPTIMESATTWOTHIRTY" to my post? It can be parsed as English words at least two ways, with one making sense. You may want to get rid of that bonus; ambiguously segmented words can be easily Googled. \$\endgroup\$ – Geobits Aug 22 '14 at 1:04
  • \$\begingroup\$ Also, any message that included any compound word would automatically qualify. This includes WAR|HEAD from your example. \$\endgroup\$ – Geobits Aug 22 '14 at 1:13
  • \$\begingroup\$ Good point. This is what I get when running on less sleep than I need haha. Was thinking of more interesting crossword boundary combinations, but obviously there was an easier solution I didn't think about. I'll take it off \$\endgroup\$ – user0721090601 Aug 22 '14 at 1:51
  • \$\begingroup\$ MOT HER and MOTH ER are also in good dictionaries, as are PAS SPORT. And if the dictionary is for spelling correction rather than for word games, it might allow LI FELON GPAS SPORT. For the purposes of giving test cases it would be better to specify a dictionary file. \$\endgroup\$ – Peter Taylor Aug 30 '14 at 14:00
  • \$\begingroup\$ @PeterTaylor true, although the idea is they'd be pushed farther down the list (fewer words being more likely, though not guaranteed, the intended message). Do you have a dictionary you know of that would be well-suited that I could link to? (come to think of it, having made a spell checker before for a highly inflected language, this is definitey something that would be truly evil for less analytical languages) \$\endgroup\$ – user0721090601 Aug 30 '14 at 14:32
  • \$\begingroup\$ I would suggest picking one from wordlist.aspell.net/12dicts-readme , although earlier questions have used others (1, 2). \$\endgroup\$ – Peter Taylor Aug 30 '14 at 15:03
1
11 12
13
14 15
95

You must log in to answer this question.

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