556
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page 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, though you can optionally add a title at the top. 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, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3993 Answers 3993

1
20 21
22
23 24
134
3
\$\begingroup\$

Simplify Rubik's Cube Moves

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

Infinite quote escaping sequence

Posted

\$\endgroup\$
15
  • \$\begingroup\$ "one of these sequences" - does this include the infinite string aa'a'a'...? Or do we have to output one of the numeric sequences? \$\endgroup\$
    – pxeger
    Jul 14 at 12:31
  • \$\begingroup\$ @pxeger one of the numeric sequences \$\endgroup\$ Jul 14 at 12:32
  • \$\begingroup\$ What does "connect the original string" mean? \$\endgroup\$
    – mousetail
    Jul 14 at 12:32
  • \$\begingroup\$ @mousetail I edited it - it should be concatenate \$\endgroup\$ Jul 14 at 12:33
  • \$\begingroup\$ I feel like the sentence is still confusing. I'm confused by the exact order. First the original string, then a "a", then the string surrounded by quotes right? \$\endgroup\$
    – mousetail
    Jul 14 at 12:35
  • \$\begingroup\$ @mousetail Yes. How should I phrase this? Is this better? \$\endgroup\$ Jul 14 at 12:36
  • \$\begingroup\$ Maybe include a example what it would look like after 1 or 2 iterations \$\endgroup\$
    – mousetail
    Jul 14 at 12:39
  • \$\begingroup\$ I don't understand the first step of the process. From the examples it just looks like you are doing the second step over and over. If I try to do it with the first step I just get an infinite sequence of 's. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 14 at 12:47
  • \$\begingroup\$ I rewrote the process as an algorithm in pseudocode. Is it clearer now? \$\endgroup\$ Jul 14 at 12:50
  • \$\begingroup\$ A worked out example of generating one of the iterations would be helpful. aa'a'a'aa''a''' is right about where you lose me, I'd like to see that one step-by-step \$\endgroup\$ Jul 14 at 12:55
  • \$\begingroup\$ It is now clearer, but I, at least, would prefer if you just described it in a normal way rather than using pseudocode. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 14 at 13:00
  • \$\begingroup\$ @WheatWizard I tried rewriting it. Is this clear? \$\endgroup\$ Jul 14 at 13:38
  • \$\begingroup\$ The commas helped a lot. I get it now :-) I still think a worked out example would be nice, but this is definitely easier to parse with the commas \$\endgroup\$ Jul 14 at 14:18
  • \$\begingroup\$ May I swap 0/1 for sequence 1? (Use 1 for non-quote, 0 for quote) \$\endgroup\$
    – tsh
    Jul 15 at 9:51
  • \$\begingroup\$ @tsh yes, I edited that in \$\endgroup\$ Jul 15 at 9:52
3
\$\begingroup\$

Every \$ n \$th repeat

Given a list of positive integers, and another integer \$ n \$, output every \$ n \$th instance of each distinct item in the list, starting with the first, in the order they appear in the original list.

For example, with \$ n = 2 \$, we will output the first instance of each item, but not the second, but we will output the third, and so on.

If \$ n = 2 \$ and the list is 4 1 3 2 3 1 6 3 4 1 1, then:

  • 1 occurs four times, so only the first and third will be kept
  • 4 occurs twice, and only the first will be kept
  • 3 occurs three times; the first and third will be kept
  • 2 and 6 only occur once each, so their first and only occurrences will be kept

Therefore, the output is 4 1 3 2 6 3 1.

This is , so the shortest code in bytes wins.

Test cases

todo

Meta

  • Related (\$ n = 2 \$, and more open ended)
  • Is this a duplicate?
  • Is this clear enough?
\$\endgroup\$
3
\$\begingroup\$

Shifted auto-sum

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

Runs of Ones (What Fun!)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Not sure if only on my browser: Width of ✓ and number are different. So last ✓ is under ] instead of 9. \$\endgroup\$
    – tsh
    Jul 26 at 5:55
  • \$\begingroup\$ Apparently, the monospace font doesn't include Unicode characters, oh well \$\endgroup\$
    – Adam
    Jul 26 at 14:47
3
\$\begingroup\$

Remove redundant parenthesis

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Tags: balanced-string, string \$\endgroup\$
    – Steffan
    Jul 25 at 23:36
  • \$\begingroup\$ If there never will be an empty pair, you probably shouldn't give (abc((123))()) as an example. \$\endgroup\$
    – Adam
    Aug 1 at 14:19
3
\$\begingroup\$

Polyglot quiz

In this challenge as a cop you will choose two programming languages A and B, as well as a non-empty string S. You are then going to write 4 programs:

  1. A program which outputs exactly S when run in both A and B.
  2. A program which outputs S in A but not in B.
  3. A program which outputs S in B but not in A.
  4. A program which doesn't output S in either A or B.

You will then reveal all 4 programs (including which number each program is) and S, but keep the languages hidden.

Robbers will try to figure out a pair of languages such that they print the correct results for the 4 programs, and cops will try to make posts that are hard to figure out while remaining as short as possible.

Warning: There is a difference in the rules from "normal"

Cops' posts here can have 4 different states:

  1. Vulnerable
  2. Cracked
  3. Safe
  4. Revealed

All cops' posts start as vulnerable. If a robber finds and posts a solution to a vulnerable post they will receive 1 point and the post will become cracked. If a post lasts 10 days in vulnerable without being solved it automatically becomes safe. A cop with a safe post may choose to reveal A and B and their safe post will become revealed. A robber can still solve a safe post, if they do they receive a point and the post becomes revealed.

Only revealed posts are eligible for scoring. Robbers are only permitted to solve vulnerable and safe posts.

Scoring

Robbers will receive 1 point for every cop answer they solve, with the goal being to gather as many points as possible.

Cops will be scored on the sum size of all four programs as measured in bytes, with the goal being to have an answer with as low a score as possible. Answers that are not revealed effectively have infinite score by this measure until they become revealed.

Languages and Output

In the interest of fairness both languages you choose must be freely available on Linux and FreeBSD. This includes languages which are Free and Open Source.

Your selected languages must predate this challenge.

Since this challenge requires that A and B produce different outputs for the same program, there is no requirement for what "counts" as a different language, the fact that they produce different outputs is enough.

Programs do not have to compile, run without error or "work" in the cases where they do not need to output S. As long as S is not the output it is valid.

Programs here should be complete programs not functions, expressions or snippets.

Running a program means is assumed to be done with no input. All four programs must be deterministic, within an environment. It is fine for example if as a part of an error the program outputs the name of the file or your host name, this is not considered non-determinism since it is determined by the enviroment running the program

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Not a comment on the challenge itself, but I like the four-state CnR system! \$\endgroup\$ Aug 8 at 11:21
  • \$\begingroup\$ Does the cop reveal which of the 4 programs satisfy which of the criteria 1-4? \$\endgroup\$
    – pajonk
    Aug 8 at 11:39
  • \$\begingroup\$ @pajonk Yes they should. I'll edit it to make it clear. \$\endgroup\$
    – Wheat Wizard Mod
    Aug 8 at 11:39
  • \$\begingroup\$ @UnrelatedString I have a feeling this is equivalent to "standard" CnR, where to become safe you need to reveal your language (or other features the challenge is about) - or are there some differences I missed? \$\endgroup\$
    – pajonk
    Aug 8 at 11:42
  • 2
    \$\begingroup\$ @pajonk In a normal CnR if a robber ever gets your answer you cannot score. However here your answer is cracked after 10 days you still get to score your answer. On a lot of CnR's people will delay the reveal to give robbers an extra chance, this ruleset allows you to do that without having to sacrifice your score. \$\endgroup\$
    – Wheat Wizard Mod
    Aug 8 at 11:45
  • \$\begingroup\$ @WheatWizard I get it now, thanks! This indeed makes more sense. \$\endgroup\$
    – pajonk
    Aug 8 at 12:16
  • \$\begingroup\$ Requiring that languages can run on FreeBSD seems unnecessarily restrictive to me, it being a pretty niche OS in the grand scheme of things. \$\endgroup\$
    – pxeger
    Aug 15 at 16:15
  • \$\begingroup\$ @pxeger The idea is that if it is Free, and runs on both linux and freeBSD it is very likely to run everywhere. And users should be able to sandbox either linux or freeBSD. It also doesn't seem like a very high bar to cross actually. If you can find a language that can't be run on freeBSD but has otherwise wide support that would make a compelling case. \$\endgroup\$
    – Wheat Wizard Mod
    Aug 15 at 17:52
3
\$\begingroup\$

A better Hexagony template

\$\endgroup\$
4
  • \$\begingroup\$ 4000th answer to this question, hooray \$\endgroup\$ Aug 10 at 12:58
  • \$\begingroup\$ "For convenience, define \$a(0)=0\$ (for zero-sized grid)." \$a(0)=3\times0(0−1)+1=1\$ though. Does the \$n=1\$ output have to be *, or are we allowed to output . instead as well? In terms of output it doesn't really make sense, but for the formula it does (and it would save me 2 bytes in my prepared solution 😅). \$\endgroup\$ Aug 11 at 11:40
  • \$\begingroup\$ @Kevin I meant size 0 grid has zero spots and size 1 has one, but now that I think of it, I don't know if Hexagony interpreter special-cases empty code or it just treats it as size 1. Something to think about... \$\endgroup\$
    – Bubbler
    Aug 11 at 14:02
  • 1
    \$\begingroup\$ @KevinCruijssen I decided to allow both :) \$\endgroup\$
    – Bubbler
    Aug 11 at 22:56
3
\$\begingroup\$

CGCC Rocket Biking

\$\endgroup\$
5
  • \$\begingroup\$ Suggestion: Split it to two challenges (validating and generating instructions). \$\endgroup\$
    – pajonk
    Mar 27 at 18:00
  • \$\begingroup\$ Good challenge! Just one question: what does may not save the input while reading mean? Does "save" just mean saving to a file, or does it include variables too? In some languages, it would be impossible to do anything with input without saving it somewhere, even if not in an explicitly named variable. \$\endgroup\$ Mar 27 at 18:02
  • \$\begingroup\$ @pajonk That's a good idea, thanks! \$\endgroup\$ Mar 28 at 12:22
  • 1
    \$\begingroup\$ @SylvesterKruin I think the idea behind that could also be written as "The program may not work on more than one character of the input at any time.", i.e. reading the entire input bit-by-bit into a var and doing transformations on that isn't allowed. I used the wording from the file directly, which wasn't a good idea as it is rather lacking in other places too. \$\endgroup\$ Mar 28 at 12:23
  • 1
    \$\begingroup\$ this does seem like an interesting challenge! I do think the while thing about only reading the input once is A) confusing and mostly unnecessary, and B) kinda against the meta consensus against unobservable requirements. The code obviously takes a single text string in somehow, but what it does with that is not controllable. Also seconding the suggestion to split this into two challenges/get rid of one of them, as determining whether it is possible is a different matter from determining how to precisely stop at the end \$\endgroup\$
    – des54321
    Apr 3 at 1:08
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\$
2
  • \$\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\$ Oct 8, 2012 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\$
    – user58826
    Jun 9, 2017 at 15:30
2
\$\begingroup\$

Polygon prefixes

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

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

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

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

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

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

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

As with all code golf, shortest code wins.


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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ What is a 101-sided figure called? "hectahenagon"? Is "hena" from the column for ones digits you mention? If so, then what is a 111-sided figure called? I'd say "hectaundecagon", but then that comes from a column where "hena" is not present. \$\endgroup\$
    – Gaffi
    Feb 11, 2013 at 11:15
  • \$\begingroup\$ @Gaffi: Yep, it's hectahenagon, from what Google says. \$\endgroup\$
    – beary605
    Feb 11, 2013 at 16:03
  • \$\begingroup\$ I am going to take this if you allow me or if you don't respond \$\endgroup\$ May 30, 2017 at 1:13
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\$
5
  • \$\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, 2013 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, 2013 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\$ Jun 10, 2013 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\$ Jun 11, 2013 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, 2013 at 14:04
2
\$\begingroup\$

Fastest Code: checking if interval pairs overlap

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

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

Example input 1:
interval x , interval y

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

Output:
Can be in any true false format.

false (They overlap)

reasoning:

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

Example input 2:

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

Output:

true (they do not overlap)

reasoning:

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

Scoring:

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

Countdown: Federal Holidays in the United States

Inspired by this question:

Christmas Countdown

Write a program or script that will countdown to the nearest U.S. federal holiday, at any given time, and will switch the display to an appropriate greeting during each holiday.

The following holidays must be tracked, and announced:

Holiday                         Date                    Greeting
==========================================================================================
New Year's Day                  Jan. 1                  Happy New Year!
Martin Luther King, Jr. Day     3rd Mon. in Jan.        Happy Martin Luther King, Jr. Day!
President's Day                 3rd Mon. in Feb.        Happy President's Day!
Memorial Day                    Last Mon. in May        Happy Memorial Day!
Independence Day                Jul. 4                  Happy Independence Day!
Labor Day                       First Mon. in Sept.     Happy Labor Day!
Columbus Day                    2nd Mon. in Oct.        Happy Columbus Day!
Veterans Day                    Nov. 11                 Happy Veterans Day!
Thanksgiving                    4th Thu. in Nov.        Happy Thanksgiving!
Christmas                       Dec. 25                 Merry Christmas!

The strings listed under "Holiday" and "Greeting" are all free. Shortcuts like "Merry X-mas!" or "Happy 4th of July" will count against you - the full and proper holiday names are free, so there's no good reason not to use them.

The following strings are also free, only when used as a label for time units or in advertising the next upcoming holiday:

days
hours
minutes
seconds
milliseconds
until
time

On any given non-holiday, the program must show a count-down timer which displays time remaining at least down to the second, and updates the display with an accurate value (according to the system clock) at least once per second. Time remaining until a holiday must be counted as the time until midnight (00:00:00) on that day.

How the days, hours, minutes, and seconds (and milliseconds, if you choose) are displayed is up to you, so long as all mandatory items are present and it is clear which numbers represent which value. Again, the strings defining units of time are free so there's no really good reason not to use them. (Though you won't be penalized for not using these strings, so long as it is still unambiguous which time units are which.) The program should also make apparent which holiday is being counted down towards.

On any given holiday, the program must cease displaying the countdown timer and instead display the appropriate greeting for that holiday from 00:00:00 until 23:59:59.

After a holiday is over, at 00:00:00 the next day, the holiday greeting must go away and be replaced with the countdown timer for the next holiday.

Answers must include:

  • Name of language
  • Score (length of golfed code, minus free characters)
  • Golfed code
  • Total length of golfed code
  • Total number of free characters used
  • Un-golfed code, with descriptive comments

The program must be capable of running accurately (according to the system clock) at any time, and must be able to run indefinitely. The only limitations to this should be those imposed by the host computer or the nature of the programming language.


Are there any additions/deletions/modifications that should be made to these rules?

I'm considering changing some of the greetings, but I'm not quite sure what to.

  • "Happy Martin Luther King, Jr. Day!" is just a mouthful and feels awkward, but shortening it to "Happy MLK Day" feels weird too - any other suggestions?
  • I'm not quite sure "Memorial Day" should really be preceded by "Happy" - thoughts?
  • Any others?
\$\endgroup\$
3
  • \$\begingroup\$ I think it would be more interesting if the strings were not free, but you still required exact match. I would like to see the compression scheme used by contestants. \$\endgroup\$ Dec 7, 2013 at 12:04
  • \$\begingroup\$ @JanDvorak This is meant to be code-golf, not kolmogorov-complexity. \$\endgroup\$
    – Iszi
    Dec 7, 2013 at 22:11
  • \$\begingroup\$ This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 14 days if you have any objections and would still like to finish and post this challenge yourself. \$\endgroup\$
    – user10766
    Nov 3, 2014 at 2:01
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\$
19
  • \$\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\$ Feb 28, 2014 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\$ Feb 28, 2014 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\$ Feb 28, 2014 at 12:11
  • \$\begingroup\$ @JanDvorak, (part of) the point of that example is that there are two AUG substrings. \$\endgroup\$ Feb 28, 2014 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\$ Feb 28, 2014 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\$ Feb 28, 2014 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\$ Feb 28, 2014 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\$ Mar 1, 2014 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\$ Mar 1, 2014 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\$ Mar 1, 2014 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\$ Mar 1, 2014 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\$ Mar 1, 2014 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\$ Mar 1, 2014 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\$ Mar 1, 2014 at 14:33
  • \$\begingroup\$ Perhaps a code-challenge where people earn x points for each complexity implemented? \$\endgroup\$
    – user10766
    Mar 2, 2014 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\$
4
  • \$\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\$ Mar 6, 2014 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\$ Mar 6, 2014 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\$ Mar 7, 2014 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\$
    – user58826
    Jun 9, 2017 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\$
8
  • \$\begingroup\$ Can the program assume that the @@ lines contain the correct line numbers? \$\endgroup\$
    – ugoren
    Mar 6, 2014 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, 2014 at 17:53
  • \$\begingroup\$ You forgot the obvious "no external tools" disclaimer. You don't want the patch $1 answer. \$\endgroup\$
    – ugoren
    Mar 6, 2014 at 17:55
  • \$\begingroup\$ @ugoren thanks for the comments, I added some further clarifications. \$\endgroup\$
    – Danny
    Mar 6, 2014 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\$ Mar 6, 2014 at 19:24
  • \$\begingroup\$ @PeterTaylor yes, updated question. \$\endgroup\$
    – Danny
    Mar 6, 2014 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\$ Mar 7, 2014 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\$
    – user58826
    Jun 9, 2017 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\$
17
  • \$\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\$ Feb 20, 2014 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\$ Feb 20, 2014 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\$ Feb 20, 2014 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, 2014 at 12:43
  • \$\begingroup\$ @ugoren, 0 is easily obtained. \$\endgroup\$ Feb 20, 2014 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, 2014 at 15:12
  • \$\begingroup\$ @PeterTaylor: I agree it is quite long, and will consider revisions to it. \$\endgroup\$ Feb 20, 2014 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\$ Feb 20, 2014 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\$ Feb 20, 2014 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\$ Feb 20, 2014 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\$ Feb 20, 2014 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\$ Mar 12, 2014 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, 2014 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\$ Mar 12, 2014 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\$ Mar 12, 2014 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\$
2
  • \$\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\$ Mar 17, 2014 at 12:42
  • \$\begingroup\$ Thanks for the feedback. I'll update accordingly later today. \$\endgroup\$
    – nrubin29
    Mar 17, 2014 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\$
8
  • \$\begingroup\$ What should be output? Only the matched words? Their positions? And directions? \$\endgroup\$ Apr 3, 2014 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, 2014 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, 2014 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, 2014 at 16:03
  • 1
    \$\begingroup\$ How does the program know where the wordsearch ends and the dictionary starts? \$\endgroup\$ Apr 3, 2014 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, 2014 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\$
    – user58826
    Jun 9, 2017 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, 2017 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\$
8
  • 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\$ Apr 3, 2014 at 9:47
  • \$\begingroup\$ @PeterTaylor Is it OK now? \$\endgroup\$
    – user80551
    Apr 4, 2014 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\$ Apr 4, 2014 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\$ Apr 4, 2014 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, 2014 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, 2014 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\$ Apr 6, 2014 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\$
    – user58826
    Jun 9, 2017 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\$
8
  • 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\$ Apr 19, 2014 at 19:05
  • \$\begingroup\$ @PeterTaylor I would like to try to solve it without regex, though. \$\endgroup\$ Apr 19, 2014 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\$
    – ashastral
    Apr 20, 2014 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\$ Apr 21, 2014 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\$
    – ashastral
    Apr 21, 2014 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\$ Apr 21, 2014 at 21:06
  • \$\begingroup\$ @impinball "Bash shouldn't almost beat APL in sheer character count in a code golf" -- why? \$\endgroup\$ Apr 24, 2014 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\$ Apr 25, 2014 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
  • 2
    \$\begingroup\$ Rather than provide alternative definitions, just link the first mention of the word matroid to the Wikipedia page. \$\endgroup\$ May 5, 2014 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\$
    – user58826
    Jun 9, 2017 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\$
6
  • \$\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\$ Jul 9, 2014 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\$ Jul 9, 2014 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\$ Jul 9, 2014 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\$ Jul 9, 2014 at 12:40
  • \$\begingroup\$ @m.buettner How is it now? Ready? \$\endgroup\$ Jul 10, 2014 at 9:21
  • \$\begingroup\$ I think so, but you should wait for two other people to tell you that. \$\endgroup\$ Jul 10, 2014 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\$
7
  • 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, 2014 at 23:57
  • \$\begingroup\$ Good catches, yes, and yes. I'll edit it in. \$\endgroup\$ Aug 5, 2014 at 23:58
  • \$\begingroup\$ If a 3 is passed in, is the house a triangular prism? \$\endgroup\$ Aug 6, 2014 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\$ Aug 6, 2014 at 18:09
  • 2
    \$\begingroup\$ Some test cases would be good. \$\endgroup\$ Aug 7, 2014 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, 2014 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\$
    – user58826
    Jun 9, 2017 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\$
5
  • 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\$ Aug 27, 2014 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\$ Aug 27, 2014 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\$ Aug 27, 2014 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\$ Nov 13, 2015 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\$ Jun 11, 2017 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\$
6
  • \$\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, 2014 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, 2014 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\$ Aug 22, 2014 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\$ Aug 30, 2014 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\$ Aug 30, 2014 at 14:32
  • \$\begingroup\$ I would suggest picking one from wordlist.aspell.net/12dicts-readme , although earlier questions have used others (1, 2). \$\endgroup\$ Aug 30, 2014 at 15:03
2
\$\begingroup\$

Marvelous Moonglyphs: Match Kana To Kanji

enter image description hereenter image description here

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

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

Overview

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

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

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

All Hiraganas ["lower case"] are

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

And the Katakanas ["upper case"] are

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

They correspond to each other in the order given above.

Scoring

Feature-challenge.

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

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

Disclaimer

Standard loopholes shall (not) apply.

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

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

Task

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

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

A simple example:

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

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

I/O source and destination

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

  • a file
  • stdin
  • network
  • keyboard

Same for the output.

Input and output format

Input:

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

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

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

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

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

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

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

  • READING only contains HIRAGANA.

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

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

Example:

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

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

Output

  • An array, or equivalent data structure.

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

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

Example:

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

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

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

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

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

Dictionary File

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

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

I also added the files on this github.


Basic Feature

Score = 20

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

A somewhat longer example:

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

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


Optional Features.

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

壱 (1) +15

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

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

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

弐 (2) +10

Support and ignore these punctuation symbols.

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

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

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

Invalid input:

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

参 (3) +10

Support , , and .

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

肆 (4) +10

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

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

伍 (5) +15

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

There shall be no before , , , and .

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

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

陸 (6) +15

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

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

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

漆 (7) +5

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

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

捌 (8) +10

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

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

So for example,

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

Punctuation symbols and KANA are be ignored for this calculation.

玖 (9) +15

Implement the MOONGLYPH doubler sign .

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

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

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

拾 (10) +10

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

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

  • きゞ
  • きぎ

陰 (Final) +20

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

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

(1)

(2)

  • 独逸 [Germany]
  • どいつ

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


Complex Example

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

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

Tutorial

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

Moved here to keep this short.


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

\$\endgroup\$
15
  • \$\begingroup\$ This sounds really interesting. A genre for such questions has been suggested before, but you might want to read the comments there voicing concerns with this concept. As for your spec, a few things are unclear to me (in addition to not knowing the first thing about Japanese): you say "READING will never contain any KATAKANA." but apparently that's not true for the dictionary files. Are you just referring to your example format here? If so that bullet point should probably not go in the input/output section. [tbc] \$\endgroup\$ Sep 1, 2014 at 15:37
  • \$\begingroup\$ Or are you referring to the output format of the program? Doesn't feature 3 preclude feature 1? Or do I just get the bonus for both features if I implement 3? And if I implement feature 3, what about feature 2? Does that then automatically apply to Parts instead of Moonglyphs? Feature 6: what do you mean by "it may appear multiple times"? Could you include an example? I also don't see how the two examples 木々 and 人々 are different. Feature 7: does our program need to handle unmatched punctuation can we just assume that punctuation characters will always agree between MOONGLYPHS and READING? \$\endgroup\$ Sep 1, 2014 at 15:42
  • \$\begingroup\$ Feature 8 is quite unclear to me. Where do you get from all of a sudden? Is that just a normal kana which gets an additional reading in this case, whereas the other two are completely new? More examples might help. Feature 12: You refer to "the last four", but you only mention four. Or are all other kana simply read as themselves while those aren't? Could you include an example for these? Also where does the discrepancy between MOONGLYPHS and READING come from in the example you already have? Is one Katakana and one Hiragana? \$\endgroup\$ Sep 1, 2014 at 15:46
  • \$\begingroup\$ Feature 15: How are readings to be treated which aren't found in the dictionary files, like those from features 8 and 12? \$\endgroup\$ Sep 1, 2014 at 15:48
  • \$\begingroup\$ And a more basic question: what is a moonglyph? Google is not very helpful in answering this (unless you meant monoglyph, but you seem to have a few too many lunar references for that to be a plausible explanation). \$\endgroup\$ Sep 1, 2014 at 17:31
  • \$\begingroup\$ Google is not always your friend, it seems. Well, I won't spoil the fun for you, just google for moonspeak. And moonglyph sounds way better than kanji. \$\endgroup\$
    – blutorange
    Sep 1, 2014 at 21:18
  • \$\begingroup\$ I have edited the question to clarify the points you addressed. Use the edit history for easier navigation. \$\endgroup\$
    – blutorange
    Sep 1, 2014 at 21:21
  • \$\begingroup\$ As beautiful as this is... it's almost a TLDR... Do you propose this to be a code-challenge? \$\endgroup\$ Sep 2, 2014 at 1:11
  • \$\begingroup\$ I had not been aware of the code challenge tag. That sounds like the right category for this. The winning criterion could be loosely based upon the number of implemented features, but also votes, CPU&Ram usage, coding style etc. I might remove/merge some features. Do you think people would be interested in this as code challenge? \$\endgroup\$
    – blutorange
    Sep 2, 2014 at 5:08
  • \$\begingroup\$ If you mean kanji, say kanji. The question's hard enough to read because of its length: there's no need to obfuscate it by deliberately avoiding the correct vocabulary. \$\endgroup\$ Sep 2, 2014 at 7:34
  • \$\begingroup\$ @blutorange No I think the scoring system as features with code-length tie breaker sounds more fun than coming up with an odd combination of features, votes and resource usage which will be impossible to balance right. I'll look at your other responses later. \$\endgroup\$ Sep 2, 2014 at 7:59
  • \$\begingroup\$ I split it into two main sections. The specs clearly defining the task, and an optional tutorial giving some background knowledge and how you might implement it in code. The latter part takes about 2/3rds. I also edited some features and changed the points rewarded (still provisional). \$\endgroup\$
    – blutorange
    Sep 2, 2014 at 9:39
  • 3
    \$\begingroup\$ @blutorange In the interest of people actually reading all of this, you might want to put the non-essential 2/3rds in a gist on GitHub and link to it. \$\endgroup\$ Sep 2, 2014 at 10:10
  • \$\begingroup\$ You're right, that's a good idea. Done. I also added the dictionary files on github for reference. \$\endgroup\$
    – blutorange
    Sep 2, 2014 at 10:49
  • \$\begingroup\$ pastebin.com/uj1krypD addresses your comments directly, but you don't need to read it. I edited the main question. \$\endgroup\$
    – blutorange
    Sep 2, 2014 at 11:03
2
\$\begingroup\$

Turn my keyboard into a piano

I'm sure we've all thought "man, wouldn't it be cool if my keyboard played musical notes as I program?". Of course, the answer to that question is a resounding no.

Regardless, it's what you're going to make.

Input

Input will be given, in real-time, on the keyboard.

The keyboard mapping that you will use is given in the diagram below. This kind of layout is used by several music programs already.

A keyboard layout, with notes assigned to several of the keys.

You can see that the bottom row (Z, X, C, V, B... ., /) represents all of the white keys, and the black keys are added on the row above (S, D, G, H, J... L, ;). This is then repeated on the two rows above, except the notes are an octave higher.

The notes C5 to E5 are repeated both on the lower rows and the upper rows.

So, if the user were to input Q (or ,) on the keyboard, middle-C (C5) should play. Similarly, if they input B, G4 should play.

The diagram above is an edited form of an image found here.

Output

The only output will be sound. The actual sound used is up to you (it could be a piano sample or the internal beeper), but it should output sound at the correct pitch.

The program should not terminate by itself - the user should be able to keep inputting notes until they get bored.

References

  • A diagram of the US keyboard layout (for comparison with the image above) can be found here.
  • A table of the frequencies of notes can be found here. The range of notes that you will be using are from C4 to E6, inclusive.

Rules and Disambiguation

  • This is , so the shortest correct implementation wins.
  • Input should be given in real-time (i.e. no pressing Enter between each inputted note).
    • There should be no greater than a 0.25 second delay between pressing a key and hearing the note.
  • Only programs that have the notes correctly mapped to the QWERTY keyboard will be accepted.
  • The only output should be sound. There should be nothing displayed (except for a mandatory console window or similar).
  • Polyphony (multiple notes playing at once) is not part of the specification.
  • The program should not terminate by itself - a user should be able to keep pressing keys and hearing notes until they decide to close it.
  • The waveform outputted is not important (it can be a beep or a piano sound or whatever you like); the pitch, however, should be accurate.
    • The file size of any sound files used will not be counted in the bytecount.
    • Please link any sound files you use with your answer.

Meta

  • There are probably some obvious things that I've forgot to explain - please point these out!
  • Also let me know if any of the wording is confusing.
  • I've assumed that the readers will at least know very basic music theory (e.g. that there are 12 semitones in an octave). Is this okay?
  • "Polyphony is not part of the specification" - polyphony is not the focus of the program, and therefore shouldn't be a consideration when submitting answers (i.e. if the shortest implementation means that one note will stop when a new note is played, then that's fine). Is this acceptable?
  • Should I exclude the use of any external libraries that are designed to play sound or designed to repeat a function at regular intervals? Should I count sound file size in the score? I'm worried that having either of these would limit the possible entries to those that can use the internal beep (so, C/C++, C#, Python, Java?...).
  • Another problem may be portability, or the lack thereof (e.g. C/C++ using the Windows API to access the Beep() function).

Really meta: answers/edits by me won't be done until the morning (approximately 9 hours from now).

\$\endgroup\$
6
  • \$\begingroup\$ Does sound need to continue until key_up, or is just a short "beep" okay no matter how long the key is pressed? \$\endgroup\$
    – Geobits
    Sep 10, 2014 at 0:26
  • \$\begingroup\$ "Of course....resounding no.... regardless.." why shit on your own question? Change it to a slightly ironic "Of course we have! Well, that's what you're going to make" \$\endgroup\$ Sep 15, 2014 at 21:37
  • \$\begingroup\$ 1,2 The wording is mostly OK Regarding @Geobits point, I think a short beep has to be acceptable. One must delve deep into API to know when a key is released (if the hardware tells at all.) Make the US keyboard requirement clearer. Take the linked image of a US keyboard, mark note names on it in color and include it in the question (I may do it for you.) Without having both on the same diagram, I found it hard to work out which notes on my Spanish keyboard end up in odd places. 3. Theory is very basic here, no need to explain Maybe link to en.wikipedia.org/wiki/Scientific_pitch_notation \$\endgroup\$ Sep 16, 2014 at 23:20
  • \$\begingroup\$ Allow libraries for sound functions. Otherwise it'll definitely be won by a language with builtins. Portability is always an issue with sound, but on codegolf.stackexchange.com/a/25242/15599 the OP did get my Windows answer working on his Linux machine after many comments. Avoid polyphony. Computer & phone keyboard matrixes can't handle it properly. If you press 1,3,7,9 on a numeric keypad and release 1, the release can't be detected because there's still an electric path through the other keys. Real music keyboards have a diode on every key, or individual wires, to avoid this problem. \$\endgroup\$ Sep 16, 2014 at 23:39
  • \$\begingroup\$ Hi, @steveverrill, thanks for your comments. I haven't really been very interested in PCCG recently so I haven't been replying/making changes. Thanks for the suggestions - I'll review the post sometime soon. \$\endgroup\$ Sep 17, 2014 at 0:07
  • \$\begingroup\$ If this is code-golf, then I suggest that you choose a set sound to make it fair for everyone. \$\endgroup\$
    – Beta Decay
    Jul 5, 2015 at 7:49
1
20 21
22
23 24
134

You must log in to answer this question.

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