464
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 '19 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – S.S. Anne Sep 26 '19 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 '19 at 13:43

2667 Answers 2667

2
\$\begingroup\$

Off-topic bullshit detector

You run a blog about astronomy and for each post there is an area for comments, where people post comments. So, when you post news about the discovery of a new exoplanet, quickly there are some people commenting about its habitability or about the methods using for their detection, and you do answer those comments, very nice.

You already have a very good spam detector that handles people who tries to post links to viagra-selling sites, so you do not worry with these.

But there is always people who you really hate and makes you very tired. People who insists to post comments that every astronomer is tired and angry to see:

  • Comments about creationism.
  • Comments about ancient astronauts theory.
  • Comments about religion arguing that instead of looking to the sky, people should look for God.
  • Comments claiming that this is all a big lie made up by governments around the world, and in fact the man never went to the Moon and the Earth is flat.
  • Comments about planet Nibiru, planet Hercolobus, planet X, planet Nemesis and similars.
  • Comments about Mayan, Sumerian, or Nostradamus profecies about the end of the world in any particular date.
  • Comments about the CIA hiding ETs in Area 51 captured from Roswell and similar stuff.
  • Comments about conspiracies by secret groups controlling or willing to control the world, like the Illuminati, the Masonry, the New World Order, and similars.
  • Useless flamewar comments that happens when people from two different groups in the previous categories disagree one with the other, posting comments that makes you sometimes doubt that intelligent life exists on Earth.

Your task is: Create a complete program that receives as input a text comment limited to 300 characters and outputs Yes/No, 0/1, Approve/Reject or something similar, rejecting the bullshit comments and accepting the valid ones.

Further, we have a few restrictions:

  • As a policy of your company, everyone may comment any post at will, without the need of prior registration, so you can't build some sort of reputation barrier system for this.
  • You can't also make comments be approved by other frequent commenters based in some reputation system. This happens because your competitor did that and the result was that the people that you want to avoid managed to take over the site being the ones with the most reputation and thus completely ruining your competitor's site. So, your boss decided that you should not build a reputation system.
  • No use of external resources in the internet.
  • You are allowed to save files in the disk or to use a database (please do not abuse this rule).
  • If you do need, you can add a training program to pre-populate the program data.
  • Your algorithm must be deterministic and consistent. I.E, in a given state for a given input, it always produce the same output. So, do not make it randomized nor use as input something like the colors of the pixels in the screen, the system clock or similar sources of entropy.
  • [Lacking a rule to avoid exploiting the score system by overfitting the test data].

Ok, people, what do you think about this question? Good? Bad? Leave a comment.

This is still lack a winning criteria. Don't know if should be , some sort of or something else. is surely out-of-question for this. What do you think?

Further, to make it testable, this will need some sort of corpus which falls in those bullshit categories and some perfectly valid as well. If you do have some suggestion on this, please, drop a comment.

\$\endgroup\$
  • \$\begingroup\$ I could say that people who post anti-creationist comments are just as annoying... \$\endgroup\$ – user10766 Mar 3 '14 at 3:35
  • \$\begingroup\$ Are comments about creationism OK when they are replying to comments about extraterrestrial life? \$\endgroup\$ – John Dvorak Mar 3 '14 at 7:23
  • \$\begingroup\$ Why no database access? Having to reimplement a database makes this challenge harder, but not more interesting. Speaking of which, code-golf requires hard criteria for accuracy (and absolute accuracy is impossible to achieve here). The usual solution is to use the popularity metric while telling people to strive for accuracy / accuracy and consciseness / accuracy and opacity / ... \$\endgroup\$ – John Dvorak Mar 3 '14 at 7:26
  • \$\begingroup\$ What makes you think the Illuminati won't use their moon-based supercomputer to figure out how to get around your filter? \$\endgroup\$ – Geobits Mar 3 '14 at 15:21
  • \$\begingroup\$ @Geobits That is easy: The man never went to the Moon, so couldn't the Illuminati do it either. In fact, it is impossible to go to the Moon because God made the Earth flat and you can imply by the Genesis that ETs do not exists. \$\endgroup\$ – Victor Stafusa Mar 3 '14 at 15:28
  • \$\begingroup\$ @JanDvorak. Ok, relaxed the databases requeriment. \$\endgroup\$ – Victor Stafusa Mar 3 '14 at 15:31
  • \$\begingroup\$ @user2509848 Ok, added this: "Useless flamewar comments that happens when people from two different groups in the previous categories disagree one with the other, posting comments that makes you sometimes doubt that intelligent life exists on Earth." \$\endgroup\$ – Victor Stafusa Mar 3 '14 at 15:32
  • \$\begingroup\$ What? No, Genesis clearly states that aliens are among us. How do you think the Illuminati got started in the first place? I'm pretty sure the "boss" in this scenario is a member anyway. He's clearly going to use your program to figure out the limits of automated bullshit detection. On topic, I like the spirit of this question, and I'd label it a code-challenge. \$\endgroup\$ – Geobits Mar 3 '14 at 15:36
  • \$\begingroup\$ @Geobits, yes I think to that it should be a code-challenge, but don't know yet how to score that. If I don't figure out a good scoring system, will default to popularity-contest. \$\endgroup\$ – Victor Stafusa Mar 3 '14 at 15:41
  • 1
    \$\begingroup\$ If you had a corpus, a basic points system seems easiest. +x for each correct reject, -y for each incorrect, something like that. If entries tie on base score, default to either code length of popularity. \$\endgroup\$ – Geobits Mar 3 '14 at 15:45
  • \$\begingroup\$ This is an interesting idea, but it does seem tough to come up with objective scoring unless there are known inputs (i.e. not "Comments about..." but "These 3 sample strings that comment about..."). But then people will just optimize to those inputs, so you'll probably get better & more interesting results if you go the popularity route and leave the detection categories open-ended as they are. \$\endgroup\$ – Jonathan Van Matre Mar 3 '14 at 15:46
  • \$\begingroup\$ +1ed Geobits for simultaneously having the same idea I did. Testing corpus is the way to go if you want it objective. \$\endgroup\$ – Jonathan Van Matre Mar 3 '14 at 15:47
  • \$\begingroup\$ OK, seems better. \$\endgroup\$ – user10766 Mar 3 '14 at 16:16
  • 3
    \$\begingroup\$ Basically you're asking for a Bayesian spam filter. The tricky thing is to write a spec for a Bayesian filter which isn't so restrictive that there's no freedom to be creative, isn't so loose that people can cheat, and doesn't require you to keep the test data secret. \$\endgroup\$ – Peter Taylor Mar 3 '14 at 16:17
  • \$\begingroup\$ @PeterTaylor Yes, the solution would probably be a Bayesian spam filter, but it does not needs to be. Yes, that spec is somewhat tricky to fine tune. Further, I still need a corpus. \$\endgroup\$ – Victor Stafusa Mar 3 '14 at 16:52
2
\$\begingroup\$

Repost from previous sandbox, I realize this is somewhat similar to the Limerick program abit higher, but this was made before that.

The Poet's Quine:

Write a quine with 1 or more rhyme scheme from http://en.wikipedia.org/wiki/Rhyme_scheme when read. The non-alphanumeric symbols aren't used for rhyming in this scheme (apart from the basic arithmetic signs like plus, minus, times and divided by), neither are comments. Words may be pronounced in any dialect, but it needs to be consistent within the same stanza (no having the first word be pronounced in a Scottish way and the second in a Welsh way).

Contest type would be popularity contest.

Thoughts on this proposal?

\$\endgroup\$
  • \$\begingroup\$ Do you guys think this is ready for posting? \$\endgroup\$ – Nzall Mar 5 '14 at 14:12
2
\$\begingroup\$

DIM, the DIM Integer Machine

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

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

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

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

Suppose the DIM has just produced an integer square: 81

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Unified format patcher

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

Clarifications

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

Extra

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

Example

/test/a.cpp

#include <iostream>
using namespace std;

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

patch.txt

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

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

Run patch

patch.exe patch.txt

/test/a.cpp

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

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

Efficient Testing for Armstrong Numbers

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

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

By contrast:

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

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

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

Winning Criteria

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

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

Create the perfect CSS reset stylesheet

Your job is to create a CSS reset stylesheet, That is, a stylesheet that you can apply to any HTML file, and the result will look the same in all webbrowsers. Because we all know that cross-browser interoperability is very important these days, and you want to make your website look pixel perfect everywhere.

The rules:

  1. You must be able to throw any valid HTML5 document at it and the result will look the same in the main browsers.
    For simplicity, you can assume that the HTML document does not contain any styles of its own or Javascript that changes anything. Just pure, static HTML that is valid HTML5.
  2. The main browsers are Firefox >= 22, Chrome >= 28 and IE >= 10.
  3. To avoid solutions like *{display:none} (which do indeed make all documents look the same in all browsers, yes) the result must be identical to the document without the stylesheet in one of the browsers.
    In other words, take your browser of choice and make the document look like that in the other browsers.

The winner is the stylesheet that works the best, again, on any HTML file that is valid HTML5 and uses no other styles. I'm not looking at efficiency. If you come up with a 100K stylesheet or one that slows the site down considerably, that doesn't matter, as long as the end result looks good.


That's the question so far. Now I have a bit of a problem with "any HTML5 document"; I know I could provide a test document that people can work with, but then you'll get answers that cater to only that particular test case, and that's not what I want. Not sure how to handle this. Ideas?
Also, I want to include Safari as a main browsers, but as I don't have a Mac, I can't test the results on it. Not sure how to handle that.

\$\endgroup\$
  • \$\begingroup\$ necolas.github.io/normalize.css ? \$\endgroup\$ – Peter Taylor Mar 14 '14 at 12:59
  • \$\begingroup\$ @PeterTaylor That breaks rule #3. \$\endgroup\$ – Mr Lister Mar 14 '14 at 13:05
  • \$\begingroup\$ The result must be identical to the document without the stylesheet in one of the browsers. I assume you have loaded a webpage without a stylesheet before? If you mean that it can have the main stylesheets, and we just need to create a modification stylesheet, you should specify that. \$\endgroup\$ – user10766 Mar 14 '14 at 16:17
  • \$\begingroup\$ @hosch250 What I mean is that I want the document to retain its basic HTML-ness, so it shouldn't look like plain text. Take this fiddle for example; open it in all browsers, and then add CSS to it so that it looks like (your favourite browser) in all other browsers. If the name of such is "modification stylesheet" rather than "reset stylesheet", I apologise. \$\endgroup\$ – Mr Lister Mar 14 '14 at 19:32
  • \$\begingroup\$ OK, I was thinking about how most HTML pages rely on CSS stylesheets to even be legible. If you took the CSS sheet off any webpage, it would not look the same; in fact, if the HTML wasn't laid out good using accessibility techniques, it wouldn't be legible. \$\endgroup\$ – user10766 Mar 14 '14 at 20:01
  • 2
    \$\begingroup\$ Pixel perfect isn't going to happen because of issues around anti-aliasing: CSS doesn't let you do things like enable ClearType on Safari/OS X or disable it on IE/Win. So the best anyone can do is somehow obtain the default stylesheets for the listed browsers (e.g. iecss.com but updated) and then find a minimal diff. \$\endgroup\$ – Peter Taylor Mar 14 '14 at 20:09
  • \$\begingroup\$ Guys, I'm not interested in solutions to the question right now. I want to know if the question is OK! Specifically if I can get away with not posting a testcase like the fiddle above. \$\endgroup\$ – Mr Lister Mar 14 '14 at 20:38
2
\$\begingroup\$

Amino Acids Matcher

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

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

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


Sample Input

TACTCGGATACT

Is split into

TAC, TCG, GAT, ACT

We now change each letter to its reciprocal

AUG, AGC, CUA, UGA

And print out the amino acids

Methionine, Serine, Leucine, Stop


This would probably be

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

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

Tic-tac-toe

Tic-tac-toe is a paper-and-pencil game for two players, played on a 3×3 grid.

Rules of Tic-tac-toe

  • The first player uses X, the second O as a symbol.
  • Tic-tac-toe is round-based. So in the first round, X has to place his symbol on any free grid cell, then O has to place his symbol on any free grid cell and so on.
  • The game is over when any player manages to get three of his symbols in any row / column or the diagonal. That player has won. So every game has at least 5 turns.
  • The game is over when all cells are full. This is a draw. So every game has at most 9 turns.

Rules of this codegolf

  • This is a . So shortest code wins.
  • Every code has to be playable. This means, at first the user has to be able to decide which player he wants to be (first / second or X / O). The other player will be the computer.
  • Optimality: The computer has to use the optimal strategy. This means, the computer can never lose (see Wikipedia).
  • Bonus: If you can play it via GUI, you get -200 characters.
  • You should provide an ungolfed version

Background

I've just seen this question on StackOverflow where somebody seems to have hard-coded an optimal player and wants to know how to reduce the size of his program. Lets see how far we can get :-)

Related questions

\$\endgroup\$
  • \$\begingroup\$ What is the difference between this question and this proposed question? I am not saying that I think that people are wrong in +1ing this and -1ing mine, I just hope to find out how I could have improved it. \$\endgroup\$ – kitcar2000 Mar 27 '14 at 16:14
  • 1
    \$\begingroup\$ @kitcar2000 it may simply be because yours was posted later. It would have been useful if the downvoter has posted a constructive comment... \$\endgroup\$ – trichoplax Apr 16 '14 at 9:23
  • \$\begingroup\$ @kitcar2000 I also think that time is important. Why did you add another proposal? \$\endgroup\$ – Martin Thoma Apr 16 '14 at 9:33
  • \$\begingroup\$ @moose Sorry, I accidentally undeleted it. \$\endgroup\$ – kitcar2000 Apr 19 '14 at 14:09
2
\$\begingroup\$

A Brief Mystery of Time

Given a cron schedule, when will the job next run?

The schedule is supplied as the usual 5 part schedule (to be fleshed out with the full spec). Support for JAN-DEC, SUN-SAT is not required - just numeric schedules - however support for ',','/' and '*' are required. You are not allowed to use the network, or external libraries/programs that implement scheduling - eg using cron itself to schedule a job to return the answer. Your answer should return the result before the time in question.

eg 3-59/15 * * * 0,7 ... should return 3 minutes past midnight next Sunday. Output should be expressed as a human-readable date (not just seconds since the epoch, or fractions of a julian day)

Notes: I had a look, we don't seem to have had cron as a puzzle before. There's going to be some choice of implementations I think-certainly between the Kernhigan cron way of iterating over every minute, or nested loops. A valid answer would be to convert the cron spec to a regexp, iterate over the next few years worth of minutes and match the output of date, for example. The code in quartz shows that you can be amazingly verbose writing this algorithm, but it's not that hard.

As specified, cron will fire at least once every 40 years if the days of the month are valid-28 years if there's no intervening century year. Unsure whether to say that the input will always produce an event, since validation is easy.

Another variant might be to ensure the solution works for the entire 40 year cycle, by saying the start/date time is input (in some format) and then providing example output. This would save me having to debug the entries, because I could pose the edge cases as tests.

My first try at posing a question.

\$\endgroup\$
  • 1
    \$\begingroup\$ In order to make this properly testable, it would probably be sensible to make it take the "current" datetime as an input rather than reading it from the clock. E.g. your example won't return 3 minutes past midnight next Sunday if run on a Sunday before 23:03. \$\endgroup\$ – Peter Taylor Apr 1 '14 at 14:58
  • 1
    \$\begingroup\$ Yep @PeterTaylor, that's the variant question at the bottom. I agree - it's not only easier to test, but easier to judge the answers because I can tell you the cases I want answered. \$\endgroup\$ – bazzargh Apr 1 '14 at 16:33
2
\$\begingroup\$

Find words in word square solver

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

A letter square

An ASCII representation I made of this:

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

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

As a test case I give custom dictionary:

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

And a test square:

OGFIR
DOMAN
ODBID
OPGES
OGFIR

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

This is so shortest code wins.

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

Collatz ...something

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

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

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

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

Thus, for n=10, we get the sequence

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

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

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

Rules

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

Input

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

Output

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

Scoring

Your score is calculated as

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

log() is the natural logarithm

Lowest score wins.

Examples

Input:

I = { 16 , 32 , 40 }

Possible outputs along with the score

C=                   Score

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

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

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


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

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


This will be tagged as


Sandbox feedback

  • Can anyone suggest a better title?

TODO

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

  • Needs a proper title.

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

Filter out repetitive lines

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

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

Sample input:

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

Output:

a simple query
ffffgggghhhh
48719999936
repetitiverepetitiverepetitiverepetitive

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


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

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

Am I a Matroid?

Input:

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

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

Output:

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

Definition:

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

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

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

Examples:

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

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

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

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

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

Specs:

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

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Rather than provide alternative definitions, just link the first mention of the word matroid to the Wikipedia page. \$\endgroup\$ – Peter Taylor May 5 '14 at 11:59
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:38
2
\$\begingroup\$

Type me out.

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

enter image description here

and provide a keypress score.

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

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

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

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

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

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

)

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

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

The Painter's Predicament

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

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

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

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

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


Input

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

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

Examples: ABCDEF, ZZZZZZ, and AAAAAC.

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

Examples: 3 ABC, 10 QRSTUVFGHJ

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


Output

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


Additional Details

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

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

n is at least 3.

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

Figure significant figures

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

Rules for finding significance

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

Input/output

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

Further information

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

Test cases

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

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

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

Old fashioned intelligence gathering

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

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

DQSIRINKSFIJATOAPQFFOUSJAR

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

QSIFIJOAPQFSJA

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

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

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

Rules

Input

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

Output

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

Other notes

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

Scoring:

  • Code golf, shortest code wins.

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

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

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

ASOIIJHAWQRATEMSDQPOYJKWEOABS (ink tape)
ASOIJWQRASDQPOKWEAS (correction tape)
I HATE MY JOB (decoded message)
\$\endgroup\$
  • \$\begingroup\$ So I get a -25 bonus just for adding "HELOVESNAPTIMESATTWOTHIRTY" to my post? It can be parsed as English words at least two ways, with one making sense. You may want to get rid of that bonus; ambiguously segmented words can be easily Googled. \$\endgroup\$ – Geobits Aug 22 '14 at 1:04
  • \$\begingroup\$ Also, any message that included any compound word would automatically qualify. This includes WAR|HEAD from your example. \$\endgroup\$ – Geobits Aug 22 '14 at 1:13
  • \$\begingroup\$ Good point. This is what I get when running on less sleep than I need haha. Was thinking of more interesting crossword boundary combinations, but obviously there was an easier solution I didn't think about. I'll take it off \$\endgroup\$ – user0721090601 Aug 22 '14 at 1:51
  • \$\begingroup\$ MOT HER and MOTH ER are also in good dictionaries, as are PAS SPORT. And if the dictionary is for spelling correction rather than for word games, it might allow LI FELON GPAS SPORT. For the purposes of giving test cases it would be better to specify a dictionary file. \$\endgroup\$ – Peter Taylor Aug 30 '14 at 14:00
  • \$\begingroup\$ @PeterTaylor true, although the idea is they'd be pushed farther down the list (fewer words being more likely, though not guaranteed, the intended message). Do you have a dictionary you know of that would be well-suited that I could link to? (come to think of it, having made a spell checker before for a highly inflected language, this is definitey something that would be truly evil for less analytical languages) \$\endgroup\$ – user0721090601 Aug 30 '14 at 14:32
  • \$\begingroup\$ I would suggest picking one from wordlist.aspell.net/12dicts-readme , although earlier questions have used others (1, 2). \$\endgroup\$ – Peter Taylor Aug 30 '14 at 15:03
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 18:27
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\$
  • \$\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\$ – Martin Ender Sep 1 '14 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\$ – Martin Ender Sep 1 '14 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\$ – Martin Ender Sep 1 '14 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\$ – Martin Ender Sep 1 '14 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\$ – Peter Taylor Sep 1 '14 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 '14 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 '14 at 21:21
  • \$\begingroup\$ As beautiful as this is... it's almost a TLDR... Do you propose this to be a code-challenge? \$\endgroup\$ – WallyWest Sep 2 '14 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 '14 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\$ – Peter Taylor Sep 2 '14 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\$ – Martin Ender Sep 2 '14 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 '14 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\$ – Martin Ender Sep 2 '14 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 '14 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 '14 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\$
  • \$\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 '14 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\$ – Level River St Sep 15 '14 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\$ – Level River St Sep 16 '14 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\$ – Level River St Sep 16 '14 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\$ – Sean Latham Sep 17 '14 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 '15 at 7:49
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 18:30
2
\$\begingroup\$

The Tetris Tournament

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

The Rules

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

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

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

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

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

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

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

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

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

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

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

There is no hold piece.

The Controller and the Bots

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

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

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

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

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

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

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

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

Example

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

enter image description here

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

Scoring

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

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

Sandbox notes

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

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

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

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

\$\endgroup\$
  • \$\begingroup\$ I think you'll find that the scores are fairly similar across runs, and therefore any of those indicators should be sufficient. \$\endgroup\$ – Nathan Merrill Aug 25 '14 at 20:08
  • \$\begingroup\$ So the game still runs at human speed? If do, I don't think level speedups matter to a computer. Also, isn't there an algorithm that runs forever for the batch of seven randomness scheme? \$\endgroup\$ – xnor Aug 28 '14 at 2:17
  • \$\begingroup\$ @xnor I think it should be a bit faster than human speed, and I could make it even faster. I don't know how feasible an optimal algorithm for the batch of seven scheme is, but even if that works for the first levels, this should still be an interesting fastest-code challenge, as that will become impossible to calculate at some point. I could also use uniform randomness or the TGM randomiser instead. \$\endgroup\$ – Martin Ender Aug 28 '14 at 6:28
  • \$\begingroup\$ It turns out the play-forever algorithm requires Hold and the next-three shown, so you're safe there for now. But there are fairly simple heuristic algorithms that seem to never lose. So, I'd guess this will become a fastest-code challenge, though it might take until level 1000 to be restricting. The nice thing about your gravity function is that a run that survives for n pieces takes O(ln n) seconds of real time, so it can test even long-lasting strategies. You should know that Tetris AI is a well-studied area, so you may want to specify whether you can use algorithms based on existing ones. \$\endgroup\$ – xnor Aug 28 '14 at 18:11
2
\$\begingroup\$

Program Survival

(king of the hill)

You are a program (in any language).

Your goal is to survive.

You exist as a single point on a 2 Dimensional toroidal map of integer coordinates. However, you are made up of letters, numbers and characters that exist within this single point.

You live on chars

Your program is made up of characters. Each character can either contribute to the execution of your program or be "saved" for later (not contribute to your program).

You are (literally) what you eat. Therefore, each point on the grid can contain 1 or more (specific) chars. If you land on a space with char(s), those chars are added to the end of your program.

However, you must also live on chars. Therefore, to move costs 1 char. Merely to exist costs 1 char every 3 turns. You may "use" chars from any part of your program.

What do programs do?

Programs can move. This means that they can move 1 unit up, left, down or right. Remember this costs 1 char.

Programs can also make other programs. This uses chars from your own program to construct a new one. Because this directly costs chars to you, there is no cost to constructing other programs. You must leave at least 20 chars in the old program.

Programs can be malicious. Programs can "attack" other programs. When two programs are next to each other, they may spend 1 char to remove a char from their enemy. They may only remove the char from the end of the enemy's program.

Programs can also enter a self-initiated coma. the program remains stationary for a minimum of 15 turns at the cost of 1 char per 7 turns.

What will programs know?

Each program will recieve the following as command line args:

  • Their own source code (as a String)
  • All cells within 5 x 5 square centered on the program
  • Any programs within vision + its coordinates (with respect to you) + the last 30 chars of its program.

How is this going to work?

This game is turn based, so on any given turn you may do any number of the following:

  1. move (limited to 1 time per turn)
  2. attack (limited to 5 times per turn)
  3. induce coma (obviously limited to 1 time)
  4. produce new programs (not limited)

If at any point your program fails to run (any error) your program dies.

Specifics

Two programs cannot occupy the same point. If a program moves to where a program is currently at, then the move is denied and the cost is revoked.

If a program chooses to create another program, the characters needed for that program will be taken from the end of the mother program. If there are not enough characters to fulfill the construction of the child program, no change will be made. Characters will be taken from the meat of your program if you fail to provide characters later in your program.

In order to make a move, you must output the following with a newline between each:

  1. move - "M(x,y),i" where abs(x+y) = 1 and i = the index of the char you want to remove.
  2. attack - "A(x,y),i where abs(x+y) = 1 and i = the index of the char you want to remove.
  3. coma - "C"
  4. reproduce - "R(x,y),s where abs(x+y) = 1 and s is the new program (as a string)

There is a _ char limit for your first program.

Should char limits be set per language? Also, how much?

Is compiling other languages on the fly difficult? I know it is possible in Java, but I am unsure in others. I have not made a controller for this yet because I am looking to see if this is a viable challenge

\$\endgroup\$
  • \$\begingroup\$ You say that we get a radius of 3 moves as the field of view. So do we really get a diamond-shaped field of view? Otherwise it sounds generally interesting, but might need some tweaking of the rules. And this should be well sandboxed - who knows what weird programs are created by removing some characters. \$\endgroup\$ – Martin Ender Sep 26 '14 at 0:02
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 18:43
  • \$\begingroup\$ Your welcome to it! If you can make a decent challenge out of this I would be quite happy to see the results. \$\endgroup\$ – Stretch Maniac Jun 11 '17 at 1:30
2
\$\begingroup\$

Orbital Mechanics [help wanted]

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

How hard can Rocket Science be, anyway?

(Storyline taken from PhiNotPi's challenges linked below)

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

*Dynamically Executable Electronically Erasable Programmable Random Access Read Only Memory

Input

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

[More details coming soon]

Output

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

\$\endgroup\$
  • \$\begingroup\$ If the burn is instant, surely the position doesn't change, and since strictly the ephemeris is the position at a given time the requirements can be met without doing any calculation? \$\endgroup\$ – Peter Taylor Oct 21 '14 at 13:40
  • \$\begingroup\$ @PeterTaylor I'm obviously not using the word 'ephemeris' correctly, then. What do you call a summary of orbit data (apoapsis, periapsis, inclination, longitude of ascending node)? \$\endgroup\$ – user16402 Oct 21 '14 at 15:07
  • 1
    \$\begingroup\$ Orbital elements? \$\endgroup\$ – Peter Taylor Oct 21 '14 at 15:36
  • 1
    \$\begingroup\$ Can I submit my answer as a kerbal space program video? \$\endgroup\$ – stokastic Oct 22 '14 at 15:50
  • \$\begingroup\$ @steveverrill The idea is to calculate how a burn (provided as input) affects your orbit, nothing else. I think you've misunderstood the question. \$\endgroup\$ – user16402 Oct 31 '14 at 15:43
  • \$\begingroup\$ Sorry, I've gone ahead and deleted my comments. I was thinking that orbital mechanics in the Cartesian system have made in the floating point cluster (and would make again) a nice challenge. But what you want to do is a simple burn calculation with the added complexity of Keplerian parameters? The challenge itself is a good one, but the problem is the Keplerian names are horrible. I've read the link but I`m still having difficulty taking in the vocabulary. Part of the problem is they don't explain periapsis and apoapsis (bottom and top of orbit!) at the beginning. \$\endgroup\$ – Level River St Oct 31 '14 at 21:28
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 18:45
2
\$\begingroup\$

Coprime Factorization of the Least Common Multiple

Given any (ordered) pair of integers (a, b), it's possible to write their least common multiple1 as a product c · d of two coprime divisors of a and b, respectively. For example, consider the pair (12, 18); the least common multiple of 12 and 18 is 36; 36 can be written as the product 4 · 9; 4 and 9 are coprime; 4 divides 12 and 9 divides 18.

For the purpose of this challenge, we'll call the pair (c, d) a coprime factorization of lcm(a, b), or simply a coprime factorization of (a, b). Note that a pair of integers may have more than one coprime factorization.

Challenge

Write a program or a function that takes a pair of integers and produces a coprime factorization of it.

Input and Output

You may read the input through STDIN, the command line, as function arguments or an equivalent method. You may assume that the input values are representable using your environment's default integer type, however you may not generally assume that their least common multiple is representable using the same type (unless your environment guarantees that.)

You may write the output to STDOUT, return it as the function's result or use an equivalent method. Note that the order of the output matters: the first output value should divide the first input value and the second output value should divide the second input value.

Scoring

This is code-golf. The shortest code, in bytes, wins.

Examples

Below is a list of input pairs and possible corresponding output pairs:

12, 18            4, 9
18, 12            9, 4
7, 13             7, 13
7, 13             -7, -13   (but not -7, 13)
1, 1              1, 1
-1, 1             1, 1
-1, -1            1, 1
30, 105           2, 105
30, 105           6, 35
30, 105           30, 7
10, 10            1, 10
10, 10            -10, -1
2, 6              2, 3
2, -6             1, 6
5, 25             1, 25
0, 8              0, 1
0, 0              0, 1   (but not 0, 0)
4, 1073741825     4, 1073741825   (but not 4, 1 if your LCM overflows to 4)

-1009612890, 633162618     138645, 70351402
140710086, -875522142      15634454, 120231
970683318, 823353894       133299, 91483766
660164274, -511130862      60014934, 85789
1048411386, 10420542       116490154, 1431
982611234, 1017084222      109179026, 139671
725309046, 922185198       99603, 102465022
65472462, -784948626       8991, 87216514
447559002, -857040426      49728778, 117693
-726750882, 708662394      66068262, 118943
133894134, -685199790      18387, 25377770
1563277915, 522665550      312655583, 18022950
873424926, 54855306        97047214, 7533
-1053523350, 347810166     117058150, 47763
855729666, 361179918       95081074, 4509
946303182, 135991350       129951, 15110150
-595150578, 475084962      81729, 52787218
886532526, 145690974       121743, 1798654
511393014, 541933722       70227, 60214858
755325450, 750082410       83925050, 20601

1 For the purpose of this challenge, lcm(n, 0) = lcm(0, n) = 0 for all n, where lcm is the least common multiple.

\$\endgroup\$
  • \$\begingroup\$ What's the point of the negative numbers? \$\endgroup\$ – feersum Oct 26 '14 at 22:59
  • \$\begingroup\$ @feersum Generality, mostly. \$\endgroup\$ – Ell Oct 26 '14 at 23:17
2
\$\begingroup\$

md5sum Creator

This is my first code golf challenge; critiquing welcome.

Your task is to create a new md5sum function. You need to output to STDOUT the input, a space or a tab character, the md5sum, then a new line. The spec for an md5sum can be found here, thanks to the IETF. For example:

1 c4ca4238a0b923820dcc509a6f75849b
2 c81e728d9d4c2f636f067f89cc14862c
... 
//hashes generated on http://www.md5.cz/
  • You may use existing libraries so long as you are not directly calling an md5sum function from within that library.
  • Output is not case sensitive (A is the same as a when it comes to an md5sum).
  • Your program/function will take in a string, and output the md5sum as a string
  • No downloading data from the Internet.
  • Code Golf, so the shortest answer wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ what should the output file be called? isn't it easier to use STDOUT? and should the character separating the number and its md5 be a tab or a space or the correct number of spaces? \$\endgroup\$ – user16402 May 30 '14 at 6:40
  • \$\begingroup\$ Is the output case-sensitive? \$\endgroup\$ – Peter Taylor May 30 '14 at 12:49
  • \$\begingroup\$ @professorfish Edited. Thanks for the input. \$\endgroup\$ – Canadian Luke May 30 '14 at 16:12
  • \$\begingroup\$ MD5 takes a sequence of octets, so how should I pack my integers? Should I pack 4 bytes in network byte order? Or little-endian? Or format each integer in ASCII? Or UTF-16? \$\endgroup\$ – kernigh Jun 19 '14 at 20:53
  • \$\begingroup\$ In that case, do you need to update your sample output? All online md5 generators I've used treat input as ASCII. \$\endgroup\$ – Peter Taylor Jun 19 '14 at 22:07
  • \$\begingroup\$ Done @PeterTaylor. Thanks \$\endgroup\$ – Canadian Luke Jun 19 '14 at 22:41
  • \$\begingroup\$ I don't see any problems with this now. \$\endgroup\$ – user10766 Nov 3 '14 at 21:46
  • 1
    \$\begingroup\$ I'd prefer if you included the relevant parts of the MD5 spec in the answer. I don't feel like reading an entire RFC to compete in the challenge, and challenges should generally be self-contained anyway. \$\endgroup\$ – Martin Ender Nov 3 '14 at 22:57
2
\$\begingroup\$

Convert Images to NetPBM format

NetPBM format is perhaps the most important image format in the history of computer graphics. Critics have called it "the format of our time." What is so revolutionary about NetPBM, you may ask? It has the unparalleled ability to store images as text files!

You have been tasked with converting images from their ancient, "lossy" format to the lossless full-color NetPBM PPM (P3) format.

The Specifics

You have a few choices as to which file format you wish to process into a PPM file.

  • JPEG
  • GIF
  • TIFF
  • PNG

Choose wisely.

The file created by your program should adhere to the P3 specifications. Here are the parts of a P3 file listed out:

  1. The characters "P3" followed by whitespace.
  2. An ASCII decimal number (like "4") which represents the image width in pixels, followed by whitespace.
  3. An ASCII decimal number (like "3") which represents the image height in pixels, followed by whitespace.
  4. An ASCII decimal number (like "255") which is to represent maximum pixel intensity. It can be an integer from 1 to 65535, inclusive. It is followed by whitespace.
  5. After this there is one line per row of pixels:
    1. Each row is separated by whitespace
    2. Each row contains one triplet for each pixel in that row, with the pixels separated by whitespace
    3. Each pixel consists of three ASCII decimal numbers separated by whitespace. These numbers represent the RGB values of that pixel, in that order. Each number must be an integer from 0-MAX, inclusive, where MAX is the number listed earlier.

Here is an example of PPM format ripped from Wikipedia:

P3
3 2
255
255   0   0     0 255   0     0   0 255
255 255   0   255 255 255     0   0   0

This is code golf: the shortest submission wins. Standard code golf rules apply.

\$\endgroup\$
  • \$\begingroup\$ I believe the actual spec limits line lengths to something like 76 characters, although certainly the GIMP will load NetPBM files which don't respect that. You might want to add a note about how much of the chosen input spec people must implement: I think that all four of those have some options which might not be widely used. \$\endgroup\$ – Peter Taylor Nov 8 '14 at 20:33
  • \$\begingroup\$ Image compression challenge: render in 0x0 1-bit greyscale! \$\endgroup\$ – feersum Nov 8 '14 at 21:21
2
\$\begingroup\$

Simple Square Packing

This is meant to be a straightforward golfing puzzle. Hopefully this hasn't been done before.

Your challenge is to figure out how large of a square is needed to fit some other squares inside of it. You input will be a list of the sizes of other squares, and the output will be the size of the needed square.

To make this problem easier (solvable) the squares will not rotate and will have integer sizes.

Example

Let's say that you have squares of sizes 2,3,3,3,4,5. This is how they can pack optimally:

555554444
555554444
555554444
555554444
55555.333
333333333
333333333
33333322.
......22.

In this case, they all fit in a size 9 square, so your program should output a 9.

Test Cases

To be added.

\$\endgroup\$
  • 3
    \$\begingroup\$ This in an NP-complete problem, so solutions will be exponential time in general. You should decide what degree of brute-forcing in solutions you're OK with. \$\endgroup\$ – xnor Nov 14 '14 at 10:09
2
\$\begingroup\$

Code Yourself a DFA

or

In this challenge, your task is to implement a deterministic finite automaton (DFA for short) that recognizes the following regular language L. The alphabet of L is x,1,2,3, and it is the set difference of (1x*|2(xx)*|3(xxx)*)* and (x|1|2|3)*1x*1x*1(x|1|2|3)*. Intuitively, the strings in the language L consist of zero or more "blocks" of the form 1xx...x, 2(xx)(xx)...(xx) or 3(xxx)(xxx)...(xxx), and three blocks of the first kind cannot occur consecutively.

The API

Your program will take two arguments from STDIN, separated by a space: a letter from the alphabet x,1,2,3, and a string that represents the current state of the DFA. The program should then write to STDOUT either A or R, a space, and a string that represents the new state of the DFA. The first letter indicates whether the new state is accepting (A) or rejecting (R). After that, the program should quit.

For example, suppose that we are checking the input string 2xx, and that the start state of my DFA is start. Then, my program is given the input 2 start, and it answers with A 2block and quits, so the next state is 2block, which is accepting. Next, the program is given x 2block, and it answers with R 2block', which is rejecting. Finally, the program is given x 2block', and it answers with A 2block. Since this state is accepting, the input is accepted (as it should be, since it is an element of L).

Rules and Scoring

Your answer should include a program and the name of its start state (which should be accepting in this case, since the empty string is in L). The score of your answer is the byte count of your program, plus three times the number of states in the DFA; the lowest score wins. A control program (written in Python 3) that checks the validity of your submission and its state count can be found here (TODO). See the README file for instructions. Finally, some additional rules:

  • Your program should be completely deterministic, and cannot read any input from any external source, other than the STDIN arguments listed above.
  • A state of the DFA is either accepting or rejecting. If your program claims that some state is accepting, and later that it's rejecting, the control program will disqualify it.
  • The states of your DFA must be strings of printable non-whitespace ASCII characters, and all such strings are valid potential states. The actual state set of your DFA is the set of states reachable from the given start state.
  • Every state of your DFA must support a transition by every letter in the input alphabet.

Sandbox questions

I'd like some comments on the scoring of this challenge, and the language L. I have tried to choose them so that there could be meaningful trade-offs between state count and byte count. Specifically, if L is too simple or the penalty on program length is too low, the best tactic is to just compress the minimal DFA. Conversely, if L is too complicated, I fear that no-one will have the energy to write a DFA for it by hand.

\$\endgroup\$
  • \$\begingroup\$ It's not clear to me why you talk about states being final or not final. The standard terminology, which is the one used by the background material you link to, is accepting vs non-accepting. I also find the description of the desired FSM hard to read: code markup (obtained with backticks) would be clearer than italics, and I'd find regex's | notation clearer than + for alternation. \$\endgroup\$ – Peter Taylor Nov 27 '14 at 18:08
  • \$\begingroup\$ @PeterTaylor: Good comments, I edited them in. \$\endgroup\$ – Zgarb Nov 27 '14 at 19:19
2
\$\begingroup\$

Balda AI in under 8192 bytes

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

The Game

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

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

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

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

Part of an example game:

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

Control, Input, Output

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

your_player_number player1_score player2_score game_status

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

PLANE
PLAN
PLANT
PLANET
TENT
*
_____
_TN__
PLANE
___TT
_____

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

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

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

4 4 T 4 5 3 5 3 4 4 4

Rules

  • Your program must be 8192 bytes or shorter at the start of the tournament. However, it may create any files and keep them between tournament games - hence, it can learn from its opponents.
  • Your program must have a name and version numbering.
  • Please provide instructions on how to run your program on Windows 8.1.
  • Libraries which provide word lists or are designed for word puzzles are not allowed.
  • Libraries created after this challenge was posted are not allowed.
  • Standard loopholes are forbidden. No web access.
  • Existing compression algorithms such as gzip are allowed, and you may use libraries to decompress them, but the decompression must be done in your program.
  • You must write a complete program, not a function.
  • If the control program detects that no words can be written, the game ends and the player with the most points wins.
  • If words can be written, but a player cannot submit a valid word in 30 seconds, they lose regardless of their score.
  • This is the official word list.
  • This is the same list, but only with five-letter words (i.e. those that can be the starting word)
\$\endgroup\$
  • \$\begingroup\$ 2k is nowhere near enough for the word list. I was very proud when I managed to write a word game for the Java4k game competition. I did it with a game design which meant that I only needed to include 4-letter words, and even so I had to chop some words to fit the word list and a bit of game logic in to 4kB (heavily compressed - uncompressed it was more like 10kB). \$\endgroup\$ – Peter Taylor Sep 4 '14 at 22:07
  • \$\begingroup\$ @PeterTaylor Let's make it 8k then? \$\endgroup\$ – user16402 Sep 5 '14 at 7:29
  • \$\begingroup\$ Maybe you should provide the word list in your computer (in txt) ? So my program just access it. Well, I have 30 seconds, sounds enough to buffer and read it. (cititation needed) \$\endgroup\$ – Realdeo Sep 5 '14 at 13:34
  • \$\begingroup\$ @Realdeo What do you mean? Your word list has to be part of your program. \$\endgroup\$ – user16402 Sep 5 '14 at 17:54
  • \$\begingroup\$ What i"m trying to say that instead of having the word list in the program, and make the program huge, just have the wordList.txt avaliable for the program to access. \$\endgroup\$ – Realdeo Sep 6 '14 at 3:13
  • \$\begingroup\$ @Realdeo No, the wordList.txt may not be available for the program to access, it must be in your program. That's part of the challenge. \$\endgroup\$ – user16402 Sep 6 '14 at 7:28
  • \$\begingroup\$ Can the input also list the words that have been used so far? In most boards, there will be words present that haven't been "used" (tenant or net in your example). \$\endgroup\$ – Geobits Oct 6 '14 at 19:08
  • \$\begingroup\$ "...or if a player cannot submit a valid word ..." Does this mean that if I'm in the lead at any point, I can just not submit a word? The game will end and I'll have more points. \$\endgroup\$ – Geobits Oct 6 '14 at 19:23
  • 1
    \$\begingroup\$ @Geobits 1. I forgot that. I'll add that in. 2. That's a big loophole. I'll change it to "if you can't submit a valid word, but there is one possible, you lose" and "if no words are possible, the game ends normally" \$\endgroup\$ – user16402 Oct 6 '14 at 20:47
2
\$\begingroup\$

Rise and Shine - Posted

\$\endgroup\$
  • \$\begingroup\$ @trichoplax I forgot to add that part to the question. Fixed. \$\endgroup\$ – globby Jan 21 '15 at 2:03
  • \$\begingroup\$ If you want results to be valid over a range of 10,000 years, what influences do you want to be taken into account? Tectonic movements? Changes in the length of the day and year? Axial precession? \$\endgroup\$ – trichoplax Jan 21 '15 at 2:08
  • \$\begingroup\$ @trichoplax Changed the date range. You may assume for the sake of the challenge that all of those are present day conditions. \$\endgroup\$ – globby Jan 21 '15 at 2:11
  • \$\begingroup\$ @trichoplax down to the second. \$\endgroup\$ – globby Jan 21 '15 at 2:18
  • \$\begingroup\$ I'd recommend being explicit in the question about what effects are not to be taken into account, to make sure there is an objective winner. Your shorter date range means other factors make less of a difference, but if measuring to the second some of them may still affect the correct answer. \$\endgroup\$ – trichoplax Jan 21 '15 at 3:27
  • \$\begingroup\$ It might even be easiest to implement a non-golfed example solution so there is a well defined answer for every input - any disputes can simply be compared to the reference implementation. \$\endgroup\$ – trichoplax Jan 21 '15 at 3:28
  • \$\begingroup\$ @trichoplax Added a resource that sums it up, would that suffice? \$\endgroup\$ – globby Jan 21 '15 at 4:40
  • \$\begingroup\$ If you state that the result given by the linked algorithm is the required result for this challenge then that would be unambiguous. Looking good. \$\endgroup\$ – trichoplax Jan 21 '15 at 5:18
  • \$\begingroup\$ @trichoplax Alrighty. \$\endgroup\$ – globby Jan 21 '15 at 5:22
  • \$\begingroup\$ @MartinBüttner they are already excluded :) \$\endgroup\$ – globby Jan 21 '15 at 19:08
  • \$\begingroup\$ The time zone bonus should be closer to 0.085. Have you seen a time zone map lately? Plus, taking DST into account? I've been thinking about making that a challenge for a while, but I think even for a dedicated challenge, this is too much to be fun to golf. \$\endgroup\$ – Martin Ender Jan 22 '15 at 20:40
  • \$\begingroup\$ @MartinBüttner good point. Removing the bonus entirely, better for a separate challenge, which I will leave up to you. \$\endgroup\$ – globby Jan 23 '15 at 5:18
  • \$\begingroup\$ Did you intend to remove the resource? Ephimerides are a seriously hard problem, so this question shouldn't be posted without some kind of exhaustive reference for validation (and ideally a good suite of test cases). \$\endgroup\$ – Peter Taylor Jan 25 '15 at 23:16
  • \$\begingroup\$ @PeterTaylor Added some test cases, does that suffice? \$\endgroup\$ – globby Jan 26 '15 at 6:02
  • \$\begingroup\$ The test cases were to supplement the reference implementation / formula, not to replace it. And are you sure about your test cases? I find it extremely odd that all of them have timezone offsets of hh:60. \$\endgroup\$ – Peter Taylor Jan 26 '15 at 9:58
2
\$\begingroup\$

Count inversions

Given a list/array/vector of 0's and 1's, count the number of inversions, which are instances of a 0 coming later than a 1. In other words, an inversion is a pair of indices (i,j) with i<j that correspond to list elements L[i]==0 and L[j]==1.

This equals the minimum number of times on needs to swap adjacent elements to sort the list.

Test cases: TODO


Questions for Sandbox: Has this really not been asked before? I searched and didn't find it. Also, is this challenge too easy? It could be made a bit harder by having list elements be general integers, or requiring generating lists with a given inversion count instead.

\$\endgroup\$
  • \$\begingroup\$ I've got a 25-char GS answer for the "general integers" case without really trying. I'll leave it to you to judge whether that's too easy. Generating lists of a given length with a given inversion count is a more interesting problem to analyse, although I suspect that the analysis turns up a relatively simple solution which everyone can copy/port. \$\endgroup\$ – Peter Taylor Jan 29 '15 at 11:38

You must log in to answer this question.

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