459
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

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

2565 Answers 2565

2
\$\begingroup\$

Fastest Code: checking if interval pairs overlap

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

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

Example input 1:
interval x , interval y

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

Output:
Can be in any true false format.

false (They overlap)

reasoning:

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

Example input 2:

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

Output:

true (they do not overlap)

reasoning:

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

Scoring:

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

Business Card Ray Tracer

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

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

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

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

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

Countdown: Federal Holidays in the United States

Inspired by this question:

Christmas Countdown

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

The following holidays must be tracked, and announced:

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

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

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

days
hours
minutes
seconds
milliseconds
until
time

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

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

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

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

Answers must include:

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

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


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

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

  • "Happy Martin Luther King, Jr. Day!" is just a mouthful and feels awkward, but shortening it to "Happy MLK Day" feels weird too - any other suggestions?
  • I'm not quite sure "Memorial Day" should really be preceded by "Happy" - thoughts?
  • Any others?
\$\endgroup\$
  • \$\begingroup\$ I think it would be more interesting if the strings were not free, but you still required exact match. I would like to see the compression scheme used by contestants. \$\endgroup\$ – John Dvorak Dec 7 '13 at 12:04
  • \$\begingroup\$ @JanDvorak This is meant to be code-golf, not kolmogorov-complexity. \$\endgroup\$ – Iszi Dec 7 '13 at 22:11
  • \$\begingroup\$ This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 14 days if you have any objections and would still like to finish and post this challenge yourself. \$\endgroup\$ – Hosch250 Nov 3 '14 at 2:01
2
\$\begingroup\$

Count unique characters in text.

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

Examples

Input:

Hello, World!

Output:

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

Input:

The quick brown fox jumps over the lazy dog.

Output:

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

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

Ultimate challenge (taken from here):

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

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

Quine with syntax highlighting


I don't really have much of an idea how to properly pose a quine challenge, or what the common syntax highlighting rules are (or aren't) for various languages. So, I figured I'd just toss this concept up here for consideration and let the community flesh it out if they think it's a good idea.

\$\endgroup\$
  • \$\begingroup\$ I'm pretty sure some languages don't even have syntax to highlight \$\endgroup\$ – John Dvorak Dec 13 '13 at 20:12
  • \$\begingroup\$ @JanDvorak Perhaps this would not quite be an "all languages" challenge, then - only languages which naturally lend themselves to syntax highlighting would be eligible. \$\endgroup\$ – Iszi Dec 13 '13 at 20:19
  • \$\begingroup\$ You also can't use a language that cannot render any decent GUI. Also, specifying the amount of syntax highlighting the program needs to generate will be hell. \$\endgroup\$ – John Dvorak Dec 13 '13 at 20:36
  • \$\begingroup\$ I don't think this question is feasible, due to the output restrictions and due to the difficulty in defining the minimum required syntax highlighting. \$\endgroup\$ – John Dvorak Dec 13 '13 at 21:09
  • \$\begingroup\$ I like this idea. I think you could specify an adequate level of highlighting with just keywords, strings or characters and numeric literals each having their own color. \$\endgroup\$ – Οurous Feb 28 '18 at 21:13
2
\$\begingroup\$

PETSCII banner

PETSCII on CodGolf.StackExchange

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

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

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

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

Animated display sample Hello world!

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

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

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

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

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

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

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

C.U.

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

McDonald's Drive-Thru

Changes from original:

  • Provided some clarification of requirements with regards to impossible ordering quantities.
  • Added specification to include total cost of order.
  • Added specification to prefer lowest cost in case of a tie for number of packages.

TODO:

  • Verify package sizes and pricing to be used for this challenge.
  • Add pricing to output samples.
  • Edit or remove "not have any limitations" rule. As currently written, it may force otherwise unnecessary bloating of code in some languages. (e.g.: PowerShell can handle numbers as uint64 to work with extremely large quantities, but it defaults to int32.)

We want to write a program to help McDonald's Drive-Thru employees assist their customers in ordering Chicken McNuggets. Chicken McNuggets only come in packs of 4, 6, 9, or 20. However, customers may not always be considering this when they pull up to the speaker.

For example, a customer might want to order 50 McNuggets but they really don't care what sort of packaging they come in - they just want to make sure they get 50 McNuggets one way or another. We want to help the customers get the best value out of their order - that is, to compose an order large enough to accommodate their needs in as few packages as possible with little to no excess.

Users will provide a request for n Chicken McNuggets. Your program's task is to provide the user with the sizes and numbers of McNugget packages needed to fulfill the order exactly. If the exact order cannot be fulfilled, the system must output an order which would meet the customer's needs with as little excess as possible. The system must also provide the total cost of the order.

Rules

  • For values of n which can be ordered exactly, output how many of each pack must be ordered to achieve the requested quantity.
  • For impossible orders (1,2,3,5,7,11), print "[requested quantity] is impossible. Have [nearest valid quantity >n]:" followed by the normal output for the nearest possible quantity >n.
  • Impossible orders cannot be hard-coded. The program must be able to determine whether fulfilling an order exactly is possible without being explicitly told that 1,2,3,5,7, and 11 are impossible.
  • Output must exclude any package sizes which do not need to be ordered.
  • Output must be in descending order of package size.
  • Output must include the sum total cost of all the packages. (Tax not included.)
  • Further layout and formatting of the output is up to you, so long as it is unambiguous.
  • Program must not have any limitations beyond those inherent to the system or programming language.
  • If there are multiple ways to assemble the order in the least number of packages, output the method which has the lowest total price.

Examples:

Input: 8
Output:

2x4

Input: 43
Output:

1x20 1x9 1x6 2x4

Input: 11
Output:

11 is impossible. Have 12: 2x6

Relevant Numberphile Link


My main concern is that this problem may be too similar to this thread:

Work out change

Otherwise, are there any changes that should be made to this?

\$\endgroup\$
  • 2
    \$\begingroup\$ My recommendation is to minimize the total cost of the order, rather than the number of packages. Based on these prices: fastfoodmenuprices.com/mcdonalds-prices, the costs are $2.99, $3.89, $4.29, and $5.00. This website lists the "9 piece" as "10 piece", I think that might be an error. \$\endgroup\$ – PhiNotPi Dec 14 '13 at 0:01
  • \$\begingroup\$ Why the restriction #3? \$\endgroup\$ – John Dvorak Dec 14 '13 at 6:12
  • \$\begingroup\$ I agree that it's too similar to the existing question. In addition, "nearest valid quantity" isn't unique, and you don't give any hint as to how to break ties. \$\endgroup\$ – Peter Taylor Dec 14 '13 at 10:17
  • 1
    \$\begingroup\$ @PeterTaylor Tiebreaker is specified as ">n", where "n" is the quantity requested by the user - that is, we want to give the user an option that will have at least as many nuggets as they want to order. \$\endgroup\$ – Iszi Dec 14 '13 at 23:37
  • \$\begingroup\$ @JanDvorak Essentially, to up the difficulty a notch. I figure it's a little trickier to catch the invalid quantities in the process of figuring out the answer if you can't write a simple if statement to match against the known quantities. \$\endgroup\$ – Iszi Dec 14 '13 at 23:42
  • \$\begingroup\$ @PhiNotPi Not sure if that's an error on the site, or a regional difference. The information I posted was based on the linked Numberphile video, which was made in the U.K.. It's also possible they may have changed the menu since then. Presuming that larger packages hold better value in terms of cost-per-nugget than smaller ones, the problem as stated should work itself out to the same goal as you've suggested. However, it might help to differentiate the challenge from the suggested duplicate if we add the total price into the expected output. \$\endgroup\$ – Iszi Dec 14 '13 at 23:45
  • \$\begingroup\$ My question is: how are you going to measure that? How large part of this knowledge are we disallowed from encoding? Can we memorize all but one? Can we special-case 1,2,3? Or, is it that anything goes as long as it either can be generalised to other Frobenius problems, or is inclusive, not exclusive? \$\endgroup\$ – John Dvorak Dec 14 '13 at 23:47
  • \$\begingroup\$ @JanDvorak The program should be able to work out for itself whether or not a given quantity is invalid - that's all there is to it. By its nature, I suppose that means solutions would be able to also handle other Frobenius problems. In fact, I was actually considering a separate "return the largest impossible quantity" problem, where users input several integers and the program outputs the largest quantity that cannot be achieved by adding multiples of those integers. \$\endgroup\$ – Iszi Dec 14 '13 at 23:53
  • \$\begingroup\$ Provided some updates to address comments. \$\endgroup\$ – Iszi Dec 15 '13 at 2:34
  • \$\begingroup\$ @Iszi Minimizing cost should serve as a tiebreaker for when there are multiple solutions with the minimum packaging. For example, look at N=36. The solution {0*4,0*6,4*9,0*20} works, but {1*4,2*6,0*9,1*20} is cheaper. (I used the costs {{4,2.99},{6,3.89},{9,4.29},{20,5.00}}) \$\endgroup\$ – PhiNotPi Dec 15 '13 at 3:07
  • \$\begingroup\$ @PhiNotPi Ah, I think I misunderstood when Peter said there wasn't a specifier for the tiebreaker. For some reason, I was thinking it was not possible for there to be a tie of that sort. Adding the price aspect definitely helps sort that out, then. Thanks. \$\endgroup\$ – Iszi Dec 15 '13 at 3:15
  • \$\begingroup\$ FWIW, it was my misreading. I failed to see the ">n". \$\endgroup\$ – Peter Taylor Dec 21 '13 at 12:01
2
\$\begingroup\$

.... . .-.. .-.. --- .-- --- .-. .-.. -..

Another Hello World challenge, this time with Morse code!

Taking no input, your program must output HELLO WORLD in audible Morse code, printing each letter as it is played. For the purpose of this challenge, the following Morse code guidelines will be followed:

Duration of sounds:

  • Dits are one time-unit long.
  • Dahs are three time-units long.
  • The gap between elements within the same character is equal to one dit.
  • The gap between characters within the same word is equal to one dah.
  • The gap between words is seven time units long.
  • The length of "one time unit" is up to the programmer, so long as it is consistent throughout the message.

Letters:

  • H: ....
  • E: .
  • L: .-..
  • O: ---
  • W: .--
  • R: .-.
  • D: -..


I'm a little iffy on that last bullet regarding duration. Should I set a hard standard, or a minimum? If so, what to?

\$\endgroup\$
  • 1
    \$\begingroup\$ Set a hard minimum for timing. Otherwise, a golfed solution might have 1 unit = 1 millisecond. \$\endgroup\$ – PhiNotPi Dec 16 '13 at 22:23
  • 6
    \$\begingroup\$ Tasks which take input are normally more interesting. \$\endgroup\$ – Peter Taylor Dec 17 '13 at 0:09
  • \$\begingroup\$ I guess that dahs need to be a continuous tone, not just two dits without a gap? \$\endgroup\$ – John Dvorak Dec 17 '13 at 6:32
  • \$\begingroup\$ @JanDvorak Correct. \$\endgroup\$ – Iszi Dec 17 '13 at 6:33
  • \$\begingroup\$ If you don't plan to post this, I would like to modify it and post it. (If you don't reply to this message within two weeks, by community standards, I am allowed to adopt the challenge.) \$\endgroup\$ – MD XF Dec 22 '17 at 2:41
  • \$\begingroup\$ @MDXF What do you suggest for modifications? \$\endgroup\$ – Iszi Jan 2 '18 at 15:18
2
\$\begingroup\$

Code Golf: counting all colors in an image

The goal of this Code Golf is to create a program that counts all colors in an image.

The input

The input will be a path to the image file.

The output

The output should be a number that indicates how much different colors your program found in the image.

The scoring

It's also important that your program supports much image formats, so I'll calculate the score based on this formula:

(character_count * 3) / (number_of_supported_image_formats * 2)

Some other rules

  • The lowest score wins
  • You're not allowed to execute an external program
  • No Internet access
  • A color doesn't just count if it's present in the palette, there really should be pixels of that color in the image.
  • You should also count pixels with 0% opacity.
  • #FFFFFF with 100% opacity is not the same color as #FFFFFF with 50% (of course, this is the same for all other colors).
  • In vector image formats, if there's a red square (for example) with 50% opacity that overlaps a blue square, then this should count as two colors: red and blue.
  • In vector image formats, in case of a gradient, the number of colors depend on which colors are used in the gradient. For example, if there is a red/yellow gradient, then you should count this as two colors: red and yellow.
  • A paletted image format is another image format than the non-paletted variant.
  • SVG 1.0 is another image format than SVG 1.1 (also count for other image formats).
\$\endgroup\$
  • \$\begingroup\$ What counts as a colour? Does a colour count as present if it's in the palette, even if there aren't any pixels of that colour? What about if it's present, but at 0% opacity? On the subject of opacity, are #ffffff at 100% opacity and #ffffff at 50% opacity the same colour? What about vector image formats: does a red square at 50% opacity partially overlapping a blue square count as two colours (red and blue) or three (red, magenta in the overlap, and blue)? What about gradients: does the number of colours depend on the size of the gradient-coloured object? \$\endgroup\$ – Peter Taylor Dec 20 '13 at 15:25
  • 1
    \$\begingroup\$ Also, what counts as an image format? If a program supports paletted PNG but not non-paletted PNG, does that count as 0 formats, 0.5 formats, or 1 format? If a program supports SVG 1.0 and SVG 1.1 does that count as 1 format or 2 formats? Etc. \$\endgroup\$ – Peter Taylor Dec 20 '13 at 15:27
  • \$\begingroup\$ @PeterTaylor: Thanks for your comments! I updated my question. \$\endgroup\$ – ProgramFOX Dec 20 '13 at 19:16
  • \$\begingroup\$ I'm sorry, but I'm afraid the core of this challenge is to be as bold as possible when counting the amount of file formats my language's standard library can handle. \$\endgroup\$ – John Dvorak Dec 20 '13 at 19:33
  • \$\begingroup\$ @JanDvorak: Of course, you should also look whether it's really worth to handle another image format, after you made sure to handle some other. If your score doesn't get lower, then it's not really worth. \$\endgroup\$ – ProgramFOX Dec 20 '13 at 19:35
2
\$\begingroup\$

Since this question is closed, I figured I'd post it here so further issues can be hammered out in Meta instead of the main site.

Known Issues:

  • Some rules seem a bit unclear to some users.
  • Clarification may be needed on what is needed to qualify for the "win percentage" bonus.
  • Win percentage bonus may not be enough to be a real incentive. (This may just depend on the language or implementation.)
  • Perhaps the win percentage bonus should be eliminated entirely, or maybe it should just be made a mandatory part of the spec.
  • It's been suggested to use a simple 1-9 numbering system for the board positions, instead of any sort of X,Y coordinates.
  • May want to allow some flexibility on the input format. (i.e.: Input must still specify the sequence of moves thus far, using whatever addressing scheme is specified in the spec, but leave the delimiters - or lack thereof - up to the developer.)
  • Exactly what is expected of the program, such as how it can figure out whose turn it is or what the output should be, seems to need some clarification.
  • Some test cases should probably be added.
  • Clarification may be needed on the matter of what parts of the game we can assume have followed the guide already.
  • Some flaws exist in the chart. (Two already mentioned in comments on the original post.) These should be identified and addressed so that proper expectations for those conditions are clearly set.
  • Original post said we would not have to account for null input (i.e.: X asking what their first move should be) but this might be a good enhancement to add.

I personally think this is a great challenge. So far, I've had a very hard time finding a lot of room for optimization and got up to probably 400 characters in PowerShell before I gave up (not even half-way through the chart yet) due to some of the above issues. I'd really like to see what some more serious golfers could do with this, once the spec is properly hammered out.


Overview

This is the XKCD tic-tac-toe cheetsheet:

enter image description here

It's rather big, I know. But it's also your most valuable resource in your challenge.

The challenge

Create a program (in your language of choice) that uses the Optimal Move Cheatsheet (henceforth OMC) to output the optimal move when given a sequence of moves.

The input

Your program will be fed a series of moves in the following fashion:

A3 A2 B2 C2 ...

Where the first combination is always X, the second O, and so on. The letter is the Y coordinate (A-C, A at the top) and the number is the X coordinate (1-3, 1 at the left).

You may assume that the given combination is following the OMC's suggestion for each move at least for the player asking for a recommendation. You can also assume that the input will never be null (at least one move has been made). You must:

  1. Figure out whether the next move is for X or O (you don't need to output this)
  2. Use the OMC to decide the next move
  3. Print the next move in the standard format A3

Optional:

You may also include the player's chance of winning (as a percentage) for 50 character discount on your score.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think a 1-9 system would be easier than any XY system, but not by too much. The biggest issue I think is that if you go by the chart (rather than formulating your own algorithm that plays the same way) you have a ton of data to enter (there are several hundred squares in the two charts). Perhaps limit the input to only sequences starting A1 B2 (or 1 5 if you use telephone keypad numbering)? That's the center square in the X chart and the top left square in the O chart. \$\endgroup\$ – Blckknght Dec 23 '13 at 5:14
  • \$\begingroup\$ @Blckknght Limiting the scope of the challenge makes it less interesting. Part of the challenge (if not the entire challenge) here is to find ways to shortcut the flow while still putting out accurate results. As for the 1-9 system, the simplification may be relatively trivial but it does help clear out some otherwise unneeded bloat since everyone will probably build in some conversion to a 1-9 system anyway to shorten the code. It also enables some other shortcuts where the same move suggestion applies to multiple situations which are mathematically related. \$\endgroup\$ – Iszi Dec 23 '13 at 19:47
  • 1
    \$\begingroup\$ My point is that the chart data so dominates the code size that winning answers will pretty much have to ignore the data in the chart and use an AI. So the challenge becomes "write a Tic-Tac-Toe AI that plays exactly like this chart", which seems less interesting to me than "use (part of) this chart to make an AI with trivial code". I already have working code for the problem and bonus in about 200 non-golfed characters of Python, but it will require many 1000s of characters of data, even if I exploit some symmetries. Even if I was willing to type all that data, an AI will beat it, I'm sure. \$\endgroup\$ – Blckknght Dec 23 '13 at 20:55
  • \$\begingroup\$ @Blckknght I'm pretty sure even a fairly straightforward implementation of the chart can be fit within about 5,000 characters - especially in a proper golfing language. IRRC, I'd finished the X portion of the chart in about 400 characters with PowerShell before I gave up on my first go at it. Even then, there was still plenty of room for optimization, and that's in a language which is far from optimal for golfing. Certainly, it's nice when you can bang out a quick answer in 15 minutes. But not every challenge has to fit in 500 characters or less. \$\endgroup\$ – Iszi Dec 23 '13 at 21:12
2
\$\begingroup\$

Implement addition using only division (code golf)

Thought you could implement division using only addition? Well try it the other way around!

Your job is to make a function or equivalent program that accepts 2 numbers and adds them using only division.

Rules

  • No importing libraries
  • You can't use anything dealing with mathematics except / and /=, (and their equivalents)
  • No bitwise operations
  • No string operations except input, output, return, and string concatenation
\$\endgroup\$
  • \$\begingroup\$ Interesting. You might have to close some loopholes, though, as some people will just create a giant lookup table. Also, some people could use string operations use perform addition. Is it going to be code golf? \$\endgroup\$ – PhiNotPi Dec 24 '13 at 16:49
  • \$\begingroup\$ @PhiNotPi I think so, thanks for the tip. \$\endgroup\$ – Timtech Dec 24 '13 at 18:42
  • \$\begingroup\$ Does "no string operations" refer to I/O as well? It's hard to do I/O without string operations of any kind \$\endgroup\$ – John Dvorak Dec 24 '13 at 19:21
  • \$\begingroup\$ @JanDvorak I want to allow I/O - how do I rephrase the question as to allow I/O without allowing math by executing strings? \$\endgroup\$ – Timtech Dec 25 '13 at 16:17
  • \$\begingroup\$ "division using only division" looks like an error... \$\endgroup\$ – Peter Taylor Dec 28 '13 at 10:17
  • \$\begingroup\$ Is this a code golf, code challenge or a popularity contest? \$\endgroup\$ – ProgramFOX Dec 28 '13 at 10:56
  • \$\begingroup\$ @PeterTaylor Thanks :) And @ ProgramFOX, it's code golf. \$\endgroup\$ – Timtech Dec 28 '13 at 14:36
  • \$\begingroup\$ @Timtech Not the number of divisions required? \$\endgroup\$ – Johannes Kuhn Dec 28 '13 at 15:03
  • \$\begingroup\$ @JohannesKuhn What are you talking about? \$\endgroup\$ – Timtech Dec 28 '13 at 15:10
  • 4
    \$\begingroup\$ Tried to calculate 0+0 - the only thing I accomplished was a division by zero ;-) \$\endgroup\$ – Howard Dec 28 '13 at 16:20
  • 2
    \$\begingroup\$ How do you prevent solutions like Array(a).concat(Array(b)).concat([0,0]).length? \$\endgroup\$ – John Dvorak Dec 28 '13 at 19:53
  • \$\begingroup\$ Is eliminating string concatenation too restrictive? Maybe only allow the built in conversions from strings to numeric types. \$\endgroup\$ – Tim Seguine Jan 14 '14 at 11:38
  • \$\begingroup\$ @Tim I guess so, maybe just disallow eval/expr. \$\endgroup\$ – Timtech Jan 14 '14 at 11:50
  • \$\begingroup\$ and would mod be allowed? \$\endgroup\$ – Tim Seguine Jan 14 '14 at 12:07
  • \$\begingroup\$ @Tim As it currently stands, no. Do you think I should add it? \$\endgroup\$ – Timtech Jan 14 '14 at 15:22
2
\$\begingroup\$

Recognize spoken numbers of .wav file

The goal of this code golf is to create a program or function that recognizes (and outputs) the spoken numbers of a Waveform Audio File (.wav).
The rules are:

  1. No network access and you are not allowed to run external programs.
  2. The input will be the file path to the WAV file, and the spoken text will only be one of these digits: one, two, three, four or five.
  3. The output must be the recognized spoken number of the WAV file.
  4. You are not allowed to use third-party libraries.
  5. This is a code golf, so the code with the smallest character count wins.
\$\endgroup\$
  • \$\begingroup\$ What do you mean by convert to text? Encode? Recognise spoken text? \$\endgroup\$ – Howard Jan 21 '14 at 18:36
  • \$\begingroup\$ @Howard: Recognize spoken text. I updated my question. \$\endgroup\$ – ProgramFOX Jan 21 '14 at 18:38
  • 1
    \$\begingroup\$ That makes it a very subjective challenge. It is quite debatable if a wav file contains recognisable text or not. I can't think of a safe way to put restrictions on the input without making it to a fixed-input kind of puzzle. \$\endgroup\$ – Howard Jan 21 '14 at 18:41
  • \$\begingroup\$ @Howard: You mean, for example, ensuring that the input will only be spoken text without background music? \$\endgroup\$ – ProgramFOX Jan 21 '14 at 18:43
  • \$\begingroup\$ This needs some explicit restrictions on input. I assume that you're assuming that the text will be English, but even then there is a lot of accent variety. Most speech-to-text programs which U.S. companies release can't handle many (if any) British accents in their first version or two. I think that the only way this can be reasonably objective is either to invert a TTS program (in which case it's boring - no errors to account for) or to specify a training text and a test text, where it gets to hear the training text read n times and then tries to interpret the test text. \$\endgroup\$ – Peter Taylor Jan 21 '14 at 18:58
  • \$\begingroup\$ Maybe it is possible if you restrict the challenge to recognise the spoken digits one, two, three and four. Although still difficult to define clearly spoken there may be small enough variation in the input. \$\endgroup\$ – Howard Jan 21 '14 at 19:09
  • \$\begingroup\$ Maybe you can make a youtube video or something similar that contains all the sound that needs to be recognized; the programs just need to cater to those sounds. \$\endgroup\$ – Justin Jan 21 '14 at 19:32
  • \$\begingroup\$ @Howard: That's a good suggestion. I updated my question. \$\endgroup\$ – ProgramFOX Jan 22 '14 at 14:14
  • \$\begingroup\$ What's a "third-party library"? Can C# programs use MS libraries, Obj-C programs use Apple libraries, etc? \$\endgroup\$ – Peter Taylor Jan 22 '14 at 16:36
  • \$\begingroup\$ @PeterTaylor: Yes, they can. \$\endgroup\$ – ProgramFOX Jan 22 '14 at 17:29
  • \$\begingroup\$ Golfing msdn.microsoft.com/en-us/library/… would make for a rather short and boring answer. \$\endgroup\$ – Peter Taylor Jan 26 '14 at 15:37
  • \$\begingroup\$ @PeterTaylor, ProgramFOX: It would make sense to forbid any libraries or programs designed for speech recognition, whether third-party or not. You might want to take a look at my earlier speech synthesis challenge for some ideas on how to word such challenges (and in the comments for some issues I should've thought of in advance). \$\endgroup\$ – Ilmari Karonen Feb 9 '14 at 10:08
2
\$\begingroup\$

Print Lorem ipsum

The goal of this code golf is to write a program that prints EXACTLY this text:

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

The rules:

  1. No external resources
  2. The shortest code in bytes wins.
\$\endgroup\$
  • 5
    \$\begingroup\$ Is there any reason to expect the answers to be fundamentally different to those to existing kolmogorov-complexity questions? \$\endgroup\$ – Peter Taylor Jan 26 '14 at 15:33
  • \$\begingroup\$ Won't the winner just post something like cout<<"/*text here*/";? This will probably be pretty boring, as the text needs to be hardcoded in. \$\endgroup\$ – Hosch250 Feb 6 '14 at 1:29
  • \$\begingroup\$ @user2509848: No, I'd expect the winner to be something that packs the text in base 29 or 32 into a raw byte string and decodes it in GolfScript or some similar language. Or possibly some PHP code that starts with <?=gzinflate(. \$\endgroup\$ – Ilmari Karonen Feb 9 '14 at 10:00
  • \$\begingroup\$ OK, but you will need to specify that in the rules. \$\endgroup\$ – Hosch250 Feb 9 '14 at 15:35
2
\$\begingroup\$

Here's my first proposal. It just occurred to me that it might be a bit difficult testing submissions without a functioning server, but maybe we can manage without? What do you people think?


The web hosting company I use has a jobs page that looks a bit like this:

Screenshot of web page

If you want to work for them, you have to calculate the correct answer and submit it through this form. But you only have a few seconds in which to do this, so you need a script to do it for you. If you submit the correct answer in time, you're then given a hash code and an email address, and are asked to email your source code to this address, using the hash code as the subject line:

Screenshot of next page after a successful submission

Using any language you like, write a script to download and submit this application form with the correct answer and hidden id field, and then email your source code with the hash code provided as the subject line. You can assume that the HTML source of the two pages is as follows:

1. http://jobs.example.com/

<!DOCTYPE html>
<html>
<head>
<title>Job Application</title>
</head>
<body>
<p>Evaluate 943 + 376 - 394 * 573 * 983 , and submit the answer with the following form.</p>
<form method="POST" action="apply.pl">
<input type="text" name="answer" value="" />
<input type="hidden" name="id" value="5d41402abc4b2a76b9719d911017c592" />
<input type="submit" name="submit" value="submit" />
</form>
</body>
</html>

2. http://jobs.example.com/apply.pl

<!DOCTYPE html>
<html>
<head>
<title>Job Application</title>
</head>
<body>
<p>Well done, that was the correct answer. Now email your source
code to jobs@example.com with the following text in the Subject
header:</p>
<p><code>1a79a4d60de6718e8e5b326e338ae533</code></p>
<p>But hurry, you only have five seconds!</p>
</body>
</html>

The only variable parts of these pages are:

  1. The sum (up to 6 numbers separated by any combination of +, - and * with spaces on both sides)
  2. The hidden id field that must be submitted with the form.
  3. The hash code on the second page

You may assume that the sum can be calculated without overflow using 32-bit integer arithmetic.

\$\endgroup\$
  • \$\begingroup\$ What's the difficulty with having a functioning server? \$\endgroup\$ – Peter Taylor Jan 28 '14 at 15:53
  • \$\begingroup\$ @PeterTaylor It won't be possible to actually test anyone's script without a server that can process these applications. This probably isn't a problem for sensible languages, but if someone submitted an answer written in Golfscript or Whitespace then I'd have no idea if it would actually work or not. \$\endgroup\$ – squeamish ossifrage Jan 28 '14 at 16:07
  • \$\begingroup\$ It won't be possible to test them anyway if you send the e-mail to jobs@example.com. I note that you haven't specified that you're after a program: I would specify that answers should be a full program which takes HTTP URL and e-mail address as command-line arguments or as separate lines on stdin; then each person can test with an e-mail address they control. If you're willing to change the URLs a bit then I can host a couple of PHP pages somewhere under cheddarmonk.org. \$\endgroup\$ – Peter Taylor Jan 28 '14 at 16:34
  • \$\begingroup\$ @PeterTaylor Ah, of course! It didn't occur to me that the email address could be separated out as input data. We'd have to change the background story a bit though. Emailing a job application to yourself seems a bit daft. \$\endgroup\$ – squeamish ossifrage Jan 28 '14 at 16:52
  • \$\begingroup\$ I don't see why. If you're allowing people advance knowledge of the full HTML structure, you can assume that they have advance knowledge of the target e-mail, and then it's just a case of promoting testable code. \$\endgroup\$ – Peter Taylor Jan 28 '14 at 17:15
2
\$\begingroup\$

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

Roman Calculator

Create a basic calculator for Roman numerals.

Requirements

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

For you to decide

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

Extra Credit

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

Sample input/output

XIX + LXXX                 (19+80)
XCIX

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

The shortest code wins.

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

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\$ I'm not sure I understand the last two points. Examples? \$\endgroup\$ – John Dvorak Feb 19 '14 at 14:50
  • 2
    \$\begingroup\$ "words are pronounced without a heavy accent or dialect" seems to me to be incompatible with "worked and borked rhyme". \$\endgroup\$ – Peter Taylor Feb 19 '14 at 17:32
  • \$\begingroup\$ That was more intended to be an example of a rhyme in general, rather than a "no heavy accent" example. I'm not a native speaker, so my pronunciation might not be totally accurate. I'll drop that rule (also could make for more interesting interpretations). \$\endgroup\$ – Nzall Feb 20 '14 at 14:53
  • \$\begingroup\$ It seems the scoring scheme actively encourages bad poetry. Maintaining a consistent rhyme scheme throughout is more difficult and better poetically, yet you penalize adjacent repetition of a scheme and give bonuses to unique schemes. Using syllables instead of feet is odd, too. A line of 12 syllables and a line of 8 can work perfectly together if one is anapests and the other iambs. I realize this is a programming site, but if you're going to call it "The Poet's Quine", let's have some real poetry!! \$\endgroup\$ – Jonathan Van Matre Feb 21 '14 at 23:05
  • \$\begingroup\$ I'm not really someone who knows a lot about poetry, but those suggestions seem good. I didn't want to make it too complicated though. you say yourself that this site is for programmers, and I doubt there are many programmers out there that know the different di-, tri- and tetrasyllable feet. maybe having a properly feeted poem can be a bonus objective? \$\endgroup\$ – Nzall Feb 22 '14 at 20:21
  • \$\begingroup\$ The biggest challenge will be finding a proper scoring system which makes sense both poetically and programmatically. It's definitely possible, but it won't be easy. Poetry is such a wide art and relies just as much on format as on content. And I don't want to force a specific kind of meter on the participants, because that's part of the challenge. \$\endgroup\$ – Nzall Feb 22 '14 at 20:35
  • 1
    \$\begingroup\$ We could also make it a popularity contest, since poetry is not about the format and content, but about evoking emotions and feelings. A popularity contest might be suited more for such a puzzle. \$\endgroup\$ – Nzall Feb 22 '14 at 20:37
  • \$\begingroup\$ Yeah, I think popularity contest solves a lot of the issues here. Of course, it also creates issues of its own, like the inexplicable number of "To be or not to be" entries on the aphorism challenge. But...lesser of two evils. :) \$\endgroup\$ – Jonathan Van Matre Feb 28 '14 at 19:32
  • \$\begingroup\$ What issues are you thinking about? maybe some extra rules can make this work. \$\endgroup\$ – Nzall Mar 4 '14 at 8:09
2
\$\begingroup\$

The shortest C program which generates the most instructions

Write a very short C program (length being defined by character count) which generates the most instructions when compiled. Of course, indicate your compiler, the version, and your operating system, and say what your program does. Linked libraries do not count!

Score

  • Base score: 1/(characters) * (instructions)
  • Bonus: if it computes something "useful," +20%

I'm fascinated by C challenges and compiler oddities, but I'm not sure about this question because of the variance you'll get between different compiler versions. Would it be acceptable to ask users to use an online resource which will compile C to assembly? I found two after a cursory search:

\$\endgroup\$
  • \$\begingroup\$ With the chars/instructions formula, the score can approach 0 (e.g. use C macros that, when nested N times, generate 2^N instructions). Also, make it clear that linked libraries don't count. \$\endgroup\$ – ugoren Feb 25 '14 at 14:57
  • \$\begingroup\$ @ugoren I'm confused about what you mean by chars/instructions, maybe I should have written instructions/characters instead of 1/characters * instructions? Noted about the linked libraries. \$\endgroup\$ – 2rs2ts Feb 25 '14 at 15:03
  • \$\begingroup\$ define DUP(x) x x and DUP(DUP(DUP(DUP(DUP(DUP(x++;)))))) - this duplicates x++ 64 times. Add another DUP and you get 128 times. \$\endgroup\$ – ugoren Feb 25 '14 at 15:20
  • 1
    \$\begingroup\$ I caught my mistake. The score can approach infinity, not zero. Still, I think, a problem. \$\endgroup\$ – ugoren Feb 25 '14 at 15:22
  • \$\begingroup\$ @ugoren Probably too many straightforward abuses to bar them all, eh? \$\endgroup\$ – 2rs2ts Feb 25 '14 at 15:29
2
\$\begingroup\$

How many pizzas do I need

Write a program that figures out the minimum number of pizzas I need to order and the amount of left overs I will have.

Requirements

  • Each pizza is 8 slices
  • Each person gets one choice of pizza topping, represented by a letter A-Z
  • Input in the format PVBC 2. Where each letter represents the choice of 1 person (e.g. P=Plain, V=Vegie, etc...), and the number is the amount of slices each person is allowed to eat. Letters can be in any order and do not need to be grouped.
  • If I don't need a full pizza I must be able to do half one topping and half another topping, the output for a half and half pizza will be denoted by X/Y where X and Y are different toppings
  • If I need multiple of a certain type of pizza they must be shown on one line (e.g. 2 x V Pizza). If there are different combinations the both result in the same, least, amount of pizzas, either output works
  • Output must match the format below of one type of pizza per line and a comma separated list of left overs. The output must show the minimum amount of pizzas and leftover possible.

Extra Credit

  • -20 - Take a 3rd argument that allows you to input the number of slices in a pizza, assume it will be an even number such that you can split it in half

Sample Input/Output

PCPVCB 3              (6 slices P, 3 slices V,  6 slices C, 3 slices B)
1 x P Pizza
1 x V/B Pizza
1 x C Pizza
2 slices P, 2 slices C, 1 slice V, 1 slice B left over

VBBCBBB 2             (10 slices B, 2 slices C, 2 slices V)
1 x C/V Pizza
2 x B Pizza
6 slices B, 2 slices C, 2 slices V left over

The 2nd example has many other combinations that could result in only 3 pizzas, this is just an example of what an output might be.

The shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ I can't say for sure, but I may have seen a similar challenge before. If not, it seems good to me. \$\endgroup\$ – Hosch250 Feb 18 '14 at 19:20
  • \$\begingroup\$ The use of the word "preferences" is confusing to me, because it suggests some kind of optimisation problem where people might get their second preference and you have to optimise for overall satisfaction. In addition, I don't find either the input or the output specification sufficiently clear. For the input, is there any guarantee that the letters are grouped (i.e. that PVP 1 will never be given as input)? And are the 4 letters given the only ones which may be used, or could there potentially be 26 different preferences? How much flexibility is there in the output? \$\endgroup\$ – Peter Taylor Feb 18 '14 at 21:12
  • \$\begingroup\$ @Danny, the one problem with this question is that because of my voracious appetite, there would be no left over pizza... ;) \$\endgroup\$ – WallyWest Feb 18 '14 at 21:15
  • \$\begingroup\$ @PeterTaylor I made edits to hopefully address all of the parts you saw that were possibly confusing. Can you look at the question again and let me know what you think. \$\endgroup\$ – Danny Feb 19 '14 at 13:44
  • \$\begingroup\$ @Danny You might want to add that you want the minimum amount of ordered pizzas/left overs - otherwise there exists a trivial solution where each person gets his own pizza (provided slices<=8). \$\endgroup\$ – Howard Feb 26 '14 at 8:19
  • \$\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:07
2
\$\begingroup\$

Golf a random Human Genome fragment with non-random features

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

Your program will:

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

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

Your program will not:

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

Sufficient randomness:

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

What-ifs:

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

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

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

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

Resurrect Adobe SubScript.

In an obscure conference procedings volume of forgotton lore, there's a quaint little paper which describes an early effort to implement a published subset of Adobe Postscript. There a line in the bibliography! :) But it cannot be found Nobody's ever heard of it. :(

Adobe Systems, "SubScript Specification", 1984.

But there's obvious utility in such a thing. So this is a hypothetical Micro-Manual Postscript, and its name shall be ASS[*]. :)

ASS is a dynamically-typed stack-based programming language with powerful graphics primitives. It has support for floating-point arithmetic, arrays and dictionaries.

The scanner reads white-space delimited tokens and attempts to interpret the token as a decimal floating-point number with optional sign (+/-). The program may (but is not required to) support exponential notation. Failing to recognize a valid number, the token becomes a name object, an atomic symbol type which is identified by the name (an "interned" string).

Types

As suggested by the scanner behavior and the operator list , there are the following object types:

  • floating-point numbers (coerced to integer where appropriate)
  • names (usually an index into a string table, for easy comparisons)
  • arrays (an indexable sequence of objects)
  • dictionaries (a key-value map of objects)
  • operators (a pointer to a built-in function)

Operators

Operators are the basic actions predefined in the dynamic name space.

Stack Manipulation

  • any   pop   -
    pop an object from the operand stack

  • any1 any2   exch   any2 any1
    exchange top two elements

  • anyN anyN-1 ... any0 N   index   anyN anyN-1 ... any0 anyN
    retrieve object from stack by position

where N is treated as an integer.

Arrays.

  • N   array   array
    create a new array of length N

  • any0 any1 ... anyN-1 array   astore   array
    fill array with objects from stack

  • array   aload   any0 any1 ... anyN-1 array
    spill contents of array onto stack

  • [   any0 any1 ... anyN-1   ]   array
    construct an array

  • array index any   put   -
    put a value into array

  • array index   get   any
    retrieve value from array

where index is treated as an integer.

The typical way to implement the array syntax is using an auxiliary type, the marktype object, and an operator counttomark. This is an implementation detail and is not strictly required but may be found to be convenient.

  • -   [   mark
    produce marktype object as a sentinel on the stack

  • mark anyN anyN-1 ... any1   counttomark   mark anyN anyN-1 ... any1 N
    count objects up to mark

Then the ] operator may be implemented in terms of the other array operators.

  • mark anyN anyN-1 ... any1   ]   array
    { counttomark array astore exch pop }

Dictionaries.

  • N   dict   dict
    create a new dictionary, an associative container with room for N name-value pairs

  • dict   begin   -
    push dictionary on dictionary stack, making names part of the dynamic name space

  • -   currentdict   dict
    push copy of topmost dictionary on dictionary stack to the operand stack

  • -   end   -
    pop and discard the topmost dictionary on the dictionary stack

  • name any   def   -
    associate name with any value in topmost dictionary

  • name   load   any
    lookup name in each dictionary in the dictionary stack from the top-down, returning the first match, or error if not found

Matrices and transformations.

A matrix is a 6-number array [a b c d e f] which represent a left-multiplying affine transformation matrix with the constant right-most column omitted.

 a b 0
 c d 0  =>  [a b c d e f]
 e f 1
  • -   matrix   matrix
    returns a new identity matrix [1 0 0 1 0 0]

  • matrix   setmatrix   -
    make matrix the current transform in the graphics state

  • -   currentmatrix   matrix
    return current transform from the graphics state

  • x y   transform   x′ y′
    transform (x,y) pair by current transformation matrix

Transforming a point involves multiplying the homogeneous vector through the transformation matrix:

          [a b 0]
[x y 1] * [c d 0] => [x' y' 1]
          [e f 1]

or, equivalently

x' = a*x + c*y + e
y' = b*x + d*y + f

Path description.

  • -   newpath   -
  • x y   moveto   -
  • x y   lineto   -
  • -   closepath   -

Clipping.

  • -   clip   -
  • -   clippath   -

Painting.

  • -   erasepage   -
  • -   fill   -
  • -   showpage   -

The fill operator is where the magic happens. This operator is responsible for performing all of the graphics algorithms in sequence:

  • Shape Mapping
    Tranform the coordinates of the path from user space to device space using the current transformation matrix.

  • Shape Clipping
    Clip the portions of the path that lie outside the clipping path.

  • Filling
    *Perform a scan-line rasterization of the (may assumed closed-) polygon described by the path into the output frame buffer.

And showpage copies the contents of the framebuffer to the actual output mechanism (window or file as described above).

... need to fill this out a little more. Math, graphics state, errors. Describing stroked lines is too much, I think. I'm not sure if it needs the forall operators for iterating through arrays and dicts. I'd like to avoid any need for overloading different types under the same operator name, and calling back to user code from an operator.

Output may be to a window, or to a file in a simple format, like pgm or even a text-file of hashes and spaces for rough bitmaps. No half-toning. Only bi-level filling of convex polygons will be required. But a program may handle more colors if desired.

This is CW in case anybody wants to help me type-in the basic operators.

Questions

Does it need anything more? Should something be removed as unnecessary? Does anyone have the spec??

Perusing my ps implementations of the graphics portions linked in the comments, I've noticed the following needed operators:

length
sub
roll
add
eq
array copy
mul
div
ne

I think it needs loops, too. It's possible to do with just recursion, of course, but loops are nice. And length, I think, needs to be polymorphic, operating on array or dict to retrieve the size for making copies and calculating indices. Add sin and cos, too.


And this would be a .

[*] The moniker "ASS" is not intended as a disparagement of Adobe Systems nor any of their stupendous intellectual property. Rather it is merely intended to express frustration at the encountered difficulty in locating this document.

\$\endgroup\$
  • \$\begingroup\$ So this is intended to be a subset of PostScript: are you going to point people at a PS spec for the nitty-gritty details about things like the precise implementation of path filling? Also, if the idea is to be minimalistic, why have both mark and [? \$\endgroup\$ – Peter Taylor Jan 11 '14 at 13:19
  • \$\begingroup\$ I'm hoping I can concisely specify everything so it's self-contained and not need to refer to a PS spec. ... Good point about mark. I suppose I can require [ and ] and suggest mark ... counttomark as a possible way to implement it. \$\endgroup\$ – luser droog Jan 11 '14 at 13:22
  • \$\begingroup\$ oh. I see what you mean now. removed mark as a separate entity. It isn't needed. \$\endgroup\$ – luser droog Jan 11 '14 at 13:32
  • \$\begingroup\$ My idea is to follow the most basic part of the original Warnock paper which is the basis of the Adobe Image Model. I've got some excerpts here. \$\endgroup\$ – luser droog Jan 11 '14 at 13:46
  • \$\begingroup\$ I don't see any way to create a non-identity matrix. \$\endgroup\$ – Peter Taylor Jan 24 '14 at 9:20
  • \$\begingroup\$ You can construct any matrix using the array notation. There should also be user space transforms: rotate, scale and translate. They're usually part of the graphics state, so I didn't put them under matrices. \$\endgroup\$ – luser droog Jan 24 '14 at 9:25
  • \$\begingroup\$ This spec from the 80s would be gold for implementing postscript. Offering a glimpse at the intermediate stage between the Warnock/Wyatt paper (which describes the image model in the syntax of the Xerox Mesa language) and the PLRM 1ed. Warnock/Wyatt has been described as "smuggling" the ideas out of Xerox. ... Ugh. I forgot to add some control structures. \$\endgroup\$ – luser droog Mar 1 '14 at 10:22
  • \$\begingroup\$ I've got implementations of paths, matrices, clipping, and filling in postscript. Perhaps I should wrap these up and just require the data structures and scanning to load and use them. \$\endgroup\$ – luser droog Mar 1 '14 at 11:33
  • \$\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:08
  • \$\begingroup\$ Thanks! ... Done. \$\endgroup\$ – luser droog Jun 11 '17 at 10:00
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\$ – Hosch250 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\$ – Hosch250 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\$

Convert input to ASCII Semaphore

With monitor resolutions getting higher and font sizes getting lower, a good programmer has to make efforts to ensure that output is accessible to the visually impaired. This can be problematic when the only display is in text. Toward this end, your assignment (if you choose to accept it) is to write a program that converts text input into ASCII art flag semaphore.

Input

  1. Your program must accept any letter in the ASCII character set from A to Z (case insensitive) and spaces.
  2. The program can accept input in any way that is convenient for the language it is written in (stdin, command line, file, etc.).

Output

  1. The program should output an ASCII art representation of the input string in flag semaphore. Follow this link to see the expected encoding.
  2. Line feeds and carriage returns should be interpreted as spaces.
  3. Numbers and other non-letters in the input may be ignored.
  4. You may use whatever ASCII art representation of the semaphore sender you like, but it must contain a person holding two flags and have distinct arms, legs, head, and flags. It must be at least 10x10 characters.
  5. Output may be either horizontal or vertical.

Example

Input: Hello

Output:

           ###
           ###
            #
 _____########
|  |       ###
|__|      ####
         # ###
        #  ###
       /   # #
      /\   # #
     /  \  # #
     \  /  # #
      \/  ## ##
                    /\
                   /  \
                  /\  /
                 #  \/
           ###  #
           ### #
            # #
          ####
         # ###
         # ###
         # ###
         # ###
         | # #
         |__ #
         |  |#
         |__|#
          ## ##
                    /\
                   /  \
                  /\  /
                 #  \/
           ###  #
           ### #
            # #
           ###
          ####
         # ###
        #  ###
       #   ###
      /    # #
     /\    # #
    /  \   # #
    \  /   # #
     \/   ## ##
                    /\
                   /  \
                  /\  /
                 #  \/
           ###  #
           ### #
            # #
           ###
          ####
         # ###
        #  ###
       #   ###
      /    # #
     /\    # #
    /  \   # #
    \  /   # #
     \/   ## ##
   /\
  /  \
  \  /\
   \/  #
        #  ###
         # ###
          # #
 _____########
|  |       ###
|__|       ###
           ###
           ###
           # #
           # #
           # #
           # #
          ## ##

Scoring

This is code golf. Shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ define "easily recognisable". Would a simple 3x3 compass (say, with a head if not covered) do? say:.o. -|. /|. ; or even: ... xx. x.. (read by lines, dots represent spaces) \$\endgroup\$ – John Dvorak Mar 6 '14 at 20:16
  • \$\begingroup\$ @JanDvorak Good catch. Edited to include distinct items that must be present and a minimum size. I'm not exactly sure how to make that rule more clear. \$\endgroup\$ – Comintern Mar 6 '14 at 20:34
  • \$\begingroup\$ Define "person holding two flags". Is what I drew a person? Is this a (lying, due to formatting issues) person: o--? Are three x's on a vertical line a person? \$\endgroup\$ – John Dvorak Mar 6 '14 at 20:43
  • \$\begingroup\$ @JanDvorak Ack! had to many tabs open and forgot to save my edit. I think number 4 for output should cover that. \$\endgroup\$ – Comintern Mar 6 '14 at 20:47
  • \$\begingroup\$ Define "distinct arms, legs, head, and flags." But I suggest allowing very small figures as well, otherwise this will turn into a kolmogorov-complexity-like question with very little of the code actually involving generating a pair of directions. \$\endgroup\$ – John Dvorak Mar 6 '14 at 20:51
  • 2
    \$\begingroup\$ Very similar to this question. The ascii art is more complex here so perhaps it's not close enough to be called a duplicate... \$\endgroup\$ – Gareth Mar 6 '14 at 22:20
  • 2
    \$\begingroup\$ I disagree with @JanDvorak: I think this would be better with a fixed output spec which must be followed exactly. That way people can golf their code rather than the output. \$\endgroup\$ – Peter Taylor Mar 6 '14 at 23:59
  • \$\begingroup\$ Standard figures seem best to me as well. If you demonstrate a full "clock" of hand positions for the standard figure, then you can require those as output. That's easier to assess than free reign for variations. \$\endgroup\$ – Jonathan Van Matre Mar 7 '14 at 0:14
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\$

Your task, should you choose to accept it, is to convert an image into ASCII art. Essentially, your program has to do precisely what picascii.com does.

Rules:

  • You must take the image from stdin or read it from a file specified in the command line.
  • You must output to stdout or to a filename specified in the command line.
  • Your program must take input in a format that ImageMagick supports. You can choose any format you want, however. If you want to read ppm images and we have to pass a jpeg through ImageMagick first to use your program, that's fine.
  • Given the above, your program itself must use only standard libraries, even for loading the image.
  • You must only output printable ASCII characters (that's 32-126 plus CR and LF).
  • You can choose in which font or setting your image should be viewed in, e.g. it might look good in a terminal but awful in a stackexchange code block, or vice versa, or maybe it only looks good with Courier New size 12, etc.
  • The largest edge of your output must be at least 25 characters and at most 200 characters long.
  • Aspect ratio must be preserved as much as possible within one fixed-width character size. e.g. if you have a 400x320 pixel image, and the fixed-width font you're outputting for is 8x13 including spacing, your output must be at least 25x12 characters, or it can be 50x25, 125x62, etc., with a maximum size of 200x98.
  • Provide at least two sample inputs & outputs with your submission. Outputs can be stackexchange code blocks or links to paste bins or screenshots of the output viewed in the environment you intended it for, etc.
  • Your score is the byte count of your source code. Lowest score wins.

However, I want the output to bear some reasonable resemblance to the input. I don't want this to be subjective. I'd rather have a hard limit that people can hack around.

Opening suggestion: maybe something like: given a font size of 8x13, if the image is converted to grayscale and quantized to 8x13 blocks, and your solution is converted to an image, scaled to fit, and also quantized to homogeneous 8x13 blocks where the value of each block is the percentage of filled-in pixels for each block, the average distance between the image blocks and your output blocks must be less than X.

\$\endgroup\$
  • \$\begingroup\$ You should delete it from the main site for now because you can't really change the rules once somebody posts an answer. You can repost it when you think it is ready. \$\endgroup\$ – Hosch250 Mar 11 '14 at 18:53
  • \$\begingroup\$ @hosch250: Good idea, just deleted it. gotta make it a good one! \$\endgroup\$ – Claudiu Mar 11 '14 at 19:02
  • \$\begingroup\$ @hosch250: The link isn't broken, it's just a deleted question, and can only be viewed by me and the mods. I wanted to not lose the link but it's there in the edit history I guess. \$\endgroup\$ – Claudiu Mar 11 '14 at 20:26
  • \$\begingroup\$ It is still in your account page too. \$\endgroup\$ – Hosch250 Mar 11 '14 at 21:55
  • \$\begingroup\$ I think this would be quite dull as a code-golf challenge. The optimal solution is to simply read every other line of a PGM file and convert each number into ASCII 32 (space) or 33 ('!') based on some threshold value. Without a code length restriction, we could add more interesting features like Floyd-Steinberg dithering and matching letter shapes to image features (e.g., using / and \ in places where diagonal likes are detected). \$\endgroup\$ – squeamish ossifrage Mar 14 '14 at 0:15
  • \$\begingroup\$ @squeamishossifrage: Hmm interesting. I was going for making an objective criterion that would make that not the optimal solution, so you'd have to use more than a few characters, but that'd be awkward. Making it a popularity contest would definitely lead to more creative solutions.. I will consider it \$\endgroup\$ – Claudiu Mar 14 '14 at 0:53
  • \$\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:19
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\$ – Hosch250 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\$ – Hosch250 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\$

music theory challenge

Create a program that takes some input in the form of frequency, waveform, and duration that generates an audio stream based on the input.

You can take input parameters however you choose, but if I input (translated to your method) 440Hz, sin(x), 3 seconds, your program should play or create a file for a sound 3 seconds long at 440 hertz on a sine wave.

Also, any output should be musically correct as far as frequency is concerned. See http://www.phy.mtu.edu/~suits/notefreqs.html for example frequencies

Since this is a popularity contest, the rest is up to you. I bid you Good programming!

Oh, and any use of external functions or APIs is ok, as long as they weren't developed specifically for this contest.

\$\endgroup\$
  • \$\begingroup\$ If the program takes "input in the form of frequency, waveform and duration" then where do linear functions fit? What do you mean "output should be musically correct as far as frequency is concerned" given that the input is frequency? Is it supposed to correct the input: "You said 494Hz but you must mean 493.88Hz"? And simple synth has been done before in various guises: see music. To differentiate this and make it non-trivial you could perhaps specify a set of basic synth operations which need to be configurable (e.g. input specifies generators, envelopes, filters, mixers). \$\endgroup\$ – Peter Taylor Mar 14 '14 at 8:39
  • \$\begingroup\$ On second thoughts, that would probably work better as a Code Review Code Challenge \$\endgroup\$ – Peter Taylor Mar 14 '14 at 9:23
  • \$\begingroup\$ @PeterTaylor I didn't even know about Code Review Code Challenges <intrigued>. Linear isn't the right word...and I think that statement is redundant anyway, so I'll nix it. \$\endgroup\$ – David Wilkins Mar 14 '14 at 12:44
  • \$\begingroup\$ Actually, I'm going to re-write this challenge...I don't know yet whether it'll be here of on CR \$\endgroup\$ – David Wilkins Mar 14 '14 at 13:07
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

You must log in to answer this question.

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