Proposed questions (sandbox) Mk II (retired)

Question

This Sandbox is being retired in favor of the newer model

Just to keep the scrolling to a reasonable level. Please feel free to continue to work or vote on question in older sandboxes.

Use this as a sandbox for new questions.

Upvote when you think a question is ready.

This question replaces the earlier Sandbox mk. I which was getting too crowded.

I actually put a draft of a question idea in the chat devoted to this - aren't two places perhaps a little confusing?
@pimvdb: Both are grassroots phenomena rather than something that a moderator started (though I whole heartily approve of both), and they seem to provide slightly different modes for seeking help. In any case, I am not going to push one over the other by diamond powered fiat; you could start a meta topic on the matter if you feel there is a pressing reason to have only one.

5 revs, 2 users 88% dmckee · Answer 1 · 2011-05-21 20:58:55Z

I attempted a problem I threw out as a suggested code-golf for 1p5.

In c, lex and yacc I needed more than 9600 characters ungolfed (fully commented, errors handled, some debugging code left in place, but some efficiency sacrificed in the name of shorter code), which seems pretty long, but c is about the most pessimal language you could choose for this problem except fortran 77 or something from the Turing Tarpit. The reference implementation can run its own build, which has some of that bootstrapping voodoo.

None-the-less, this is a relatively big project, and I don't want to post it unless people feel it is both well specified and interesting.

As yet there is no validation script, and I am not sure how one could be written as the acceptable output order could be post-order depth first or post-order breadth first and there is a left-first vs. right-first ambiguity on both. What a bother.

Aside: I'm quite proud of the lex and yacc part of my code, as I consider it spiffy.

A minimal implementation of the make (1) utility.

By minimal I mean,

No built in rules, and no pattern or suffix rules.
No variables and therefore no variable assignment or manipulations; also no variable expansion which includes no expansion of environment variables.
No automatic variables like $< and $@.

This only leaves constructs (called rules) of the form

<target> ":" <prerequisite>* "\n" ["\t" <action> "\n"]*

Where each <target> and <prerequisite> is a whitespace delimited string which may (or may not) represent a filename. Empty lines have no effect and "#" marks the beginning of a end of line comment (the sequence "#[^\n]*\n" should be treated as "\n" so it does not interfere with rules; this has the side effect of making "#" illegal in targets, prerequisites and actions). Colons are prohibited in identifiers.

The program should take its input from the standard input or by reading a file called "makefile" - implementer's choice. The program then attempts to "build" every target named on the command line. Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error and cause the program to exit before execution of any rules. In the event that no target is named on the command line, default to building the first target in the input.

Duplicate targets may (not must!) be treated as an error.

A target is deemed already built if

It names an existing file and
All its prerequisites are fulfilled

Otherwise it is built by

Building all unfulfilled prerequisites then
Running each <action> sequentially in the order they appear in the input, and if the action returns an exceptional exit state, stopping the program.

A prerequisite is deemed fulfilled if

The prerequisite represents an existing file and
The prerequisite is built and
The target is "newer" than the (fully built) prerequisite

A target is deemed "older" (i.e. not "newer") than its prerequisite if one of

Both represent files and the prerequisite has been modified more recently than the target.
The target does not represent an existing file, and the prerequisite does.

apply.

Authors on systems which do not support fork/exec semantics may write a batch file or script which is invoked as the program terminates, but that script must stop on the first unsuccessful action.

Sample Input

# Babymake compatible makefile for babymake
all:babymake

babymake : lex.yy.o  y.tab.o  babymake.o 
    cc -o babymake lex.yy.o y.tab.o babymake.o

babymake.o : babymake.c babymake.h
    cc -c babymake.c

lex.yy.o: lex.yy.c y.tab.h
    cc -c lex.yy.c

lex.yy.c : babymake.l
    lex babymake.l

y.tab.o: y.tab.c babymake.h
    cc -c y.tab.c

y.tab.c : babymake.y  
    yacc -d babymake.y

clean:
    rm -f babymake.o  lex.yy.o  y.tab.o

cleaner: clean # just testing end of line comments
    rm -f y.tab.c y.tab.h
    rm -f lex.yy.c

bogus: boguser 
    echo "building bogus" # test in another context

Sample output

$ ./babymake < babymake.example cleaner
 rm -f babymake.o  lex.yy.o  y.tab.o
 rm -f y.tab.c y.tab.h
 rm -f lex.yy.c
$ ./babymake < babymake.example all    
 cc -c babymake.c
 yacc -d babymake.y
 cc -c y.tab.c
 lex babymake.l
 cc -c lex.yy.c
 cc -o babymake lex.yy.o y.tab.o babymake.o
$ ./babymake < babymake.example    
$ ./babymake < babymake.example bogus
ERRNO: 2: No such file or directory No rule to make target 'boguser'.

The program should take it's input from the standard input or by reading a file called "makefile" - is this a choice for the implementer to make? Or should the program read stdin, and if it's empty then look for makefile? Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error before execution of any rules. Does "generate an error" include aborting, such that no rules are executed? Running each in sequence - missing "action"? Why is the sample input indented? I'll do an edit for punctuation in a bit.
In order. (1) Implementer's choice. Should be more specific. (2) Generate an error means abort; this is a unix utility after all. (3) The sample is indented because I made a strenuous effort to get the tabs in, and MarkDown just doesn't like tabs. Also there is a new sample input that has some comments in.
More questions: 1) The target is "newer" than the prerequisite once *they* have been fulfilled. What does this mean? Should this text be talking about building? 2) Under what circumstances can a target be built twice?
1) Yes and 2) Standard make never builds a target twice, and neither does my reference implementation. But I should probably say that it is or is not allowed. Do you have a feeling in the matter?
Saying that it is not allowed is probably best. Otherwise there's potential for stuff to go wrong when multiple targets depend on clean, which will never be built because it doesn't correspond to a file.
I suggest that the golf exercise be to simply output the list of commands to run, not actually execute them. Will make testing much easier.
This is awesome. But I'm too mystified by make to even fathom how it goes about it. I'd never be able to do this without stealing ideas from other posts on the page. But then, I'm an introverted intuitive, intellectuals would probbly have an easier time. :) I haven't checked, but .. I say it's ready to post. Answers may be slow in coming, but they WILL come!
@luserdroog my reference implementation builds a directed graph (in the technical sense) of dependencies and then starts evaluating from the named target(s). I can't recall right off if I enforced acycality on the graph or not. I believe that real make insists on it.
That doesn't semm quite so unfathomable. I suppose the variables and impicit rules are responsible for much of the mystery.

5 revs, 2 users 98% Gareth · Answer 2 · 2011-07-17 10:25:59Z

up vote 4 down vote

Facial Recognition [Posted]

edited Jul 17 '11 at 10:25

community wiki

5 revs, 2 users 98%
Gareth

Any input or advice on ambiguities or possible test cases appreciated. – Gareth Jun 20 '11 at 10:20

Gah! I thought it looked reasonably simple until I saw the last example. "Where two or more faces overlap priority should be given to the larger face" could be clarified to indicate that both faces should be cleared and boxed, but that the one with priority is effectively stuck on top of the other. +1 because it is an interesting problem and I think the test cases do make the intent unambiguous. – Peter Taylor Jun 21 '11 at 7:42

Ah, there's one corner case not explicitly covered in the spec or tests. What happens when a face is right up against an edge and one or more edges of the box go out of bounds? – Peter Taylor Jun 21 '11 at 16:11

1

@Peter Thanks, I've added an example to cover that 'boundary' case now. I was tempted to just put in a guarantee that no face would touch a boundary, but where's the fun in making it easier? :-) – Gareth Jun 21 '11 at 18:19

Looks interesting. If you need test scripts, poke me in chat ;-) – Joey Jun 21 '11 at 20:44

"Z is an odd integer greater than 3" -- this is incorrect. (Should be >= 3) – BlaXpirit Jul 7 '11 at 10:25

@BlaXpirit Well spotted, thanks. – Gareth Jul 7 '11 at 14:58

4 revs PleaseStand · Answer 3 · 2011-06-06 02:31:57Z

Code Golf: Code 39 Barcode Scanner (Posted)

Code 39, developed in 1974, is one of the most commonly used symbologies, or types, of barcodes, although it is the UPC/EAN system that is most often seen in retail sales. Code 39 barcodes can encode uppercase letters, numbers, and some symbols and are trivial to print from computer software using a special font. This led to their widespread commercial and industrial use (e.g. company ID badges, asset tracking, factory automation).

Create the shortest program or function to read a Code 39 barcode in any orientation from a 512x512 pixel grayscale image; the barcode might not be aligned horizontally or vertically.

Your program shall accept a standard image file format and produce the data encoded in the barcode as its standard output or return value (not including any start/stop character).
No image contains more than one valid Code 39 barcode, and no barcode encodes a space character (ASCII 32).
If no valid Code 39 barcode is shown in the image, the program shall output a single question mark (?).

I have prepared a JavaScript reference implementation and test suite of images in PNG format, both with valid barcodes and without. The reference implementation, which fails only 3 of 46 test cases in most recent Web browsers, is intended to show one possible decoding algorithm, not to strictly conform to the above specification.

A valid submission passes at least 80% of these tests and takes no more than one minute to do so for each image on a reasonably fast CPU (e.g. 2.6 GHz quad-core). My reference implementation passes 93% of tests and processes each image within 10 seconds (on my desktop PC running Google Chrome).

I'm thinking...fill a Hough accumulator, select the slice corresponding to the preferred orientation, read off wide and narrow bands...(?)...profit! All of which might be moderately long. Have you got a reference implementation?
+1 for quite thorough test cases and lots of effort going into the task initially. I'm not quite sure how viable this is as a code golf, though. As dmckee noted already, many parts of this are quite complex and long to implement.
Well, it is a big'un for code-golf... but I think the task is simpler than @dmckee takes it to be. I kinda like it.
@dmckee: I now have a ~100 line ungolfed JavaScript decoder program that only gets a few barcodes wrong. It's in a Git repository on my hard drive; I'll get it onto Github or elsewhere in a day or two.

3 revs Joey · Answer 4 · 2011-06-18 15:56:25Z

up vote 3 down vote

Jump and run [Posted]

It's not as trivial as it sounded initially.

edited Jun 18 '11 at 15:56

community wiki

3 revs
Joey

	Similar on Stack Overflow: Code Golf: 2D Platformer. – dmckee♦ May 22 '11 at 1:05
	Still, it's not the same and looks like it'll take some thought to solve reliable. I like it. – dmckee♦ May 22 '11 at 1:06
	DP looks like a way forward. – Peter Taylor May 22 '11 at 21:58
	I think ASCII art input is fine for this one. But, I think the problem is a bit too simple. Making the distance for R and J mutually prime would enable the addition of backward running and backward jumps (with, of course, different distances!) Which would yield problems with interesting search spaces. – MtnViewMark May 27 '11 at 0:44
	Is a run prefered over a jump? – Yet Another Geek May 27 '11 at 16:31
	Yet: If a run would lead you into a pit, then yes. The bottoms of those pits are lined with spiky spikes and that could prove unhealthy. Apart from that, no. – Joey May 27 '11 at 16:33
	I meant a J = RRRR when moving along highground. So I was just wondering if one should prefer to do RRRR than one J. But aside that this problem is fairly simple to solve, and if R is as good as J then it is even simpler. Oh and how can it be solved with Regex? My solution takes above linear time, assuming a precompiled (DFA) regex, a solution would run in linear time. – Yet Another Geek May 28 '11 at 7:05
	Yet Another Geek: I could solve some trivial examples with an equally trivial regex, however one could construct input that fails to be solved that way. Still, the results by now indicate that it's still very easy to do with an RE. – Joey Jun 19 '11 at 9:20

2 revs Gareth · Answer 5 · 2011-07-29 21:52:45Z

up vote 3 down vote

Mate in one [Posted]

edited Jul 29 '11 at 21:52

community wiki

2 revs
Gareth

7 revs rmckenzie · Answer 6 · 2011-05-27 21:42:55Z

BlackJack Part II

Repost from the original sandbox

As I had a blast working on the original KOTH challenge, I wanted to come up with another. For me, the fun of these AI challenges is in refining a comparatively simple bot which plays a very simple game subtly. Due to the probabilistic nature of card games, I think that blackjack could be an interesting KOTH game just like TPD.

Rules

Bots play at tables of four (4) competitors and one (1) dealer
One (1) shoe is shared by all players and the dealer until it is exhausted, at which point a new randomly shuffled deck will be added and play will continue. The bots ARE NOT (at present) NOTIFIED of the addition of this new deck. [TODO? would make card-counting a LOT harder...]
There is a buy-in of 10 per round, and cards are free
There is no bet maximum as bets are between the player and the house, yet the bot must have sufficient chips to immediately finance the bet.
Perfect/ideal hand has a score of 21
All face cards have a value of 10
All numeric cards are worth their number
Aces are worth 11 or 1. this will be dealt with automatically by the framework, not the bots.
Scores in excess of 21 which use an ace as 11 force the ace to reduce in value to 1 scores in excess of 21 which cannot be coerced below the threshold of 21 "bust" the bot
The dealer draws until he busts, or excedes a score of 17.
The stake is subtracted from chips, so the chips value is the number of credits which are available to the bot for betting.

Dealing and Bot Moves

When the game starts, each player is iteratively dealt one card, and has the $10 buy-in fee/minimum bet subtracted from their chips.
Then (in the same order as they were dealt to) each bot is executed as described in the "Programmer's Interface" section and must make a move or stand. Betting is considered a move. NOTE THAT BETTING DOES NOT AFFECT BOTS' ABILITY TO MAKE FURTHER MOVES. It is very possible to bet and then draw a card, and it is possible to draw multiple cards and them bet before standing.

Programmer's Interface and Legal Moves

As documented in the CardShark class:

#   DOCUMENTATION
#       INPUT SPECIFICATION
#          $ ./foo.bar <hand-score> <hand> <visible cards> <stake> <chips>
#          <hand-score>     is the present integer value of the player's hand.
#          <hand>           is a space-free string of the characters [1-9],A,J,Q,K
#          <visible cards>  every dealt card on the table. when new shoes are brought
#                           into play, cards drawn therefrom are simply added to this list
#                           !!! THE LIST IS CLEARED AT THE END OF HANDS, NOT SHOES !!!
#          <stake>          the  number of chips which the bot has bet this hand
#          <chips>          the number of chips which the bot has
#       SAMPLE INPUT
#          $ ./foo.bar 21 KJA KQKJA3592A 25 145
#
#       OUTPUT SPECIFICATION
#          "H"|"S"|"D"|"B"  (no quotes in output)
#          "H"              HIT - deal a card
#          "S"              STAND - the dealer's turn
#          "D"              DOUBLEDOWN - double the bet, take one card. FIRST MOVE ONLY
#          "B 15"           BET - raises the bot's stakes by $15.

Winner Selection

The winner would be the author of the bot which consistently accrued the most chips over a yet-to-be determined number of tables and rounds.

Code Review github

Issues & ToDo

None! (no known problems at least)

~~PS. How do I tag questions/answers?~~ thanks @dmckee [ai-player] [card-game] [koth]

Version History

5/25 - 0020 - v1 - updated code on GitHub which fixes a bug with the dealer. DD still scores monstrously for unknown reasons. tagged this post (with any luck).

5/25 - 0800 - v2 - bugfix on github which correctly implements DoubleDown, resulting in drastically reduced scores from the double-nut bot.

5/25 - 0920 - v3 - updated the test case to match the input specification. Added the rules for the dealer.

5/25 - 1100 - v4 - added a description of the table and shoe system.

5/25 - 1620 - v5 - added an explanation of the betting and card-dealing system, major status update.

5/27 - 1700 - v6 - ready to roll the contest...

Tags: [ai-player] and [card-game] seem naturals, though neither exists on the site as yet. What else?
The SAMPLE INPUT isn't consistent with the INPUT SPECIFICATION - do the args include the current score or not? How many decks of cards should we assume to be used? Does <chips> include <stake>? How does the AI dealer play? Is each bot-dealer pair using a separate shoe (so that when I stand the dealers cards are drawn fairly from all those not included in <hand> and <visible-cards>)? When does betting occur?
should players be notified of the number of decks in play, or not? The issue is that decks are dealt from until the deck is exhausted, then the "cannot pop from empty list" error signals the creation of a new shuffled deck then continues drawing as if nothing had happened. This means that multiple decks can be in play at once, but the statistical worst-case is that each player has three or four cards, which makes between fifteen and twenty samples split between two decks of 52. It shouldn't make a difference to score-based bots, but card-counters will need to detect or be notified of the chage

SHiNKiROU · Answer 7 · 2011-05-28 19:03:40Z

Number-Hopper Maze

http://cstheory.stackexchange.com/questions/6358/solving-a-number-hopper-maze

Write a program that solves the Number-Hopper maze described above. The input will be an ASCII art description of the maze

+------------+-----+
|x        |18|28  o|
| +--+--+ |  +--+--+
| |13|29|4|27|10|25|
| |  |  +-+--+     |
| |  |       +-----+
| |  |    |      23|
| |  +----+  ------+
| |  |    |        |
| |  | |  +------  |
| |  | |           |
| |  | |  ------+--+
| |  | |        |8 |
| |  | +-----+  |  |
| |  |  22|9 |  |  |
| |  +----+  |  |  |
|       14|11|     |
+---------+--+-----+

- and + are walls, they are interchangeable
x is the starting point
o (lowercase O) is the destination

The numbers are hop points, to hop from number A to B, you must pay the cost of abs(A - B), the positive difference between two numbers. The goal is to find the solution with the minimum cost.

The solution for the example above is x-13-11-9-8-29-28-o, with total cost of 4.

The input of the program will be the ASCII art of the maze, and the output is the sequence of numbers to hop, with the total cost. In the format of x-13-11-9-8-29-28-o 4

To qualify, you algorithm must be under or equal to O(n^2). Include an informal proof if others suspect you.

I don't want to see pure brute-force solutions where obvious bad solutions such as moving in loops and making total 99999-steps for a small maze are included in the solution space.

The shortest code wins.

So the problem is (1) build a undirected, weighted graph from the ASCII maze and (2) find the shortest path from "x" to "o" in that graph. Part 2 is cookbook stuff and languages which have good support for it may have a real advantage, but part one presents some choices. I like it.
You should drop the complexity test, and worry about brute force. Just give an example big enough that brute force won't work. With this kind of problem, it should easy enough to give such a maze.

2 revs nharren · Answer 8 · 2011-05-31 22:48:47Z

Egyptian Pyramids [Posted]

The Great Pyramid of Giza, the largest pyramid in Egypt, is not only the oldest of the Seven Wonders of the Ancient World, but it is also the only one to remain largely intact. The Egyptian Pyramids can take up to 20 years to build and are so big that Al-Aziz Uthman, son of the great Saladin who crushed the Crusaders, had to give up demolishing the Great pyramids of Giza because it was deemed too great a task. The Egyptian pyramids were mostly built as tombs for the country's Pharaohs and their consorts during the Old and Middle Kingdom periods (c. 2686-1690 BCE), and as of 2008, 138 Egyptian pyramids have been discovered.

The task is to create a program which inputs a sequence of distances separated by a space, and produces 10x10 text pyramids separated by those distances. A distance of 1 is equal to two characters.

A text pyramid will look like this:

         /\
        /--\
       /----\
      /------\
     /--------\
    /----------\
   /------------\
  /--------------\
 /----------------\
/------------------\

If the input consists of only a line break, then one pyramid will be produced, as above. For each pyramid, pyramids to the left are displayed as if they were in front.

Example I

Input:

4 3 1

Output:

         /\      /\    /\/\
        /--\    /--\  /--\-\
       /----\  /----\/----\-\
      /------\/------\-----\-\
     /--------\-------\-----\-\
    /----------\-------\-----\-\
   /------------\-------\-----\-\
  /--------------\-------\-----\-\
 /----------------\-------\-----\-\
/------------------\-------\-----\-\

Example II

Input:

0 9

Output:

         /\                /\
        /--\              /--\
       /----\            /----\
      /------\          /------\
     /--------\        /--------\
    /----------\      /----------\
   /------------\    /------------\
  /--------------\  /--------------\
 /----------------\/----------------\
/------------------\-----------------\

Example III

Input:

Output:

         /\                    /\
        /--\                  /--\
       /----\                /----\
      /------\              /------\
     /--------\            /--------\
    /----------\          /----------\
   /------------\        /------------\
  /--------------\      /--------------\
 /----------------\    /----------------\
/------------------\  /------------------\

The application to fulfill these requirements in the fewest amount of characters is the winner.

Reference: Wikipedia.org

migimaru · Answer 9 · 2011-08-17 12:50:46Z

Self-Golfing Code

I think it would be interesting to have a challenge to write a program where the program could "golf" itself. The hard part is coming up with the right specification and restrictions to keep the submissions interesting. What I'm currently thinking of are the following:

The input is the program's own source code, provided in stdin or as a file.
The output is a "golfed" version of the source code that must be shorter by at least 5 characters.
If the "golfed" version was run with the same input (the original source code), the output must be the same as the output of the original.
If the program was run with any other program (in the same language) as the input, the output must still be syntactically valid. It does not need to shorten it, and it does not matter if the resulting program doesn't function the same way.
If the program's source code was placed within another program (in the same language), then running the golfer on that other program would still "golf" the embedded source code in the same way. (The idea here is to prevent something like a program that just deletes the first five characters of itself.)
The score is the length of the original "ungolfed" program.

Is this challenge interesting enough in a variety of languages? And what other cheap tricks need to be guarded against?

It is a little interesting too me that you basically require the submitter to turn in a incompletely golfed submission. Or is this not intended to be a [code-golf]?
It's still a code-golf. That's part of the challenge - you still have to golf it but leave room so that your program can still golf itself a little more. I think it would be interesting to see what approaches people take for this.
Alternately, I could count the length of the golfed result instead of the original program, though I'm not sure it will make much difference in determining the winner.
I think I need to add a rule that prevents a simple trim() operation to eliminate whitespace at the end of a line. Would it be sufficient to say "all trim()-like operations are banned"?
why ban trim()? You force competitors to manually implement an otherwise built-in function. Besides, would "r_( )+$__" or an equivalent trivial trailing space replacement be counted?
Hmm, I'm not sure what to do about it now. I don't like having to ban a function, but trim() allows for single statement solutions where you just read in the first line and trim off 5 trailing spaces. I was hoping for a challenge that would be more interesting.
You'll need to ban comments, unnecessarily long variable names, all unnecessary whitespace... And even then I can see fairly easy cheap tricks like unnecessary variable swaps (`\` in GolfScript). Hard to make this robust enough.
@Peter Taylor I was already planning on banning comments. I don't think replacing variable names is non-trivial, though it might be in some languages. Whitespace is a big problem, though. In the end, I agree that this question doesn't seem like it'll work out.

dmckee · Answer 10 · 2011-05-29 21:07:15Z

Generate a Texting Dictionary

Old fashioned cell phones were and are used heavily as texting platforms, unfortunately the keyboard has only 12 + a few buttons, and is therefor ill-suited to naive text entry.

Common solutions make use of the traditional telephone coding (generally with a modest extension for 'q' and 'z'):

2: a,b,c
3: d,e,f
4: g,h,i
5: j,k,l
6: m,n,o
7: p(,q),r,s
8: t,u,v
9: w,x,y(,z)

In this case we are interested in the one-press-per-letter schemes that offer up words matching words on a frequency basis. That is if the user type "4663" the phone will offer up words like "good", "home", "gone", "hood", "hoof", etc that code to 4663 in order of their frequency.

Your task is to read one or more input files and generate a frequency sorted dictionary that could be used to implement this scheme.

Inputs

All input will be plain ASCII text.
You may accept input from named files, the standard input, or other conventional source supported by your implementation language, but there must be some mechanism to process several files in a single run.
Non-letter, non-whitespace characters should be stripped from the input, this means that contractions will be coded without their apostrophe: "don't" --> "dont" --> 3668
Words are a sequence of letters separated surrounded by whitespace
All whitespace (space, tab, newline, beginning-of-file, end-of-file) is equivalent.

Output

The output consists of a ASCII text stream
You may direct this to a file, the standard output, or any other conventional destination supported by your implementation language
The output should consist of one line for each string of digits corresponding to at least one word in the input.
Each line should consist of the digit string and a list of all corresponding words sorted by frequency with the most frequent coming first. A sample line of output would be
```
4663 good home gone hood hoof
```
Tokens (digit strings and corresponding words) should be separated by a single space.
Equally frequent words may be sorted in any order.

Test Case and Validation

[Still to come. The test case will contain no frequency ties to ease the evaluation]

Expanding Expressions [Posted]

Given an expression of one-letter variables ([a-z]), operators (*, +, &) and parenthesis, expand it using the following axioms:

a * b != b * a
a * b * c = (a * b) * c = a * (b * c)
a + b = b + a
a + b + c = (a + b) + c = a + (b + c)
a * (b + c) = a * b + a * c
a & b = b & a
a & (b + c) = a & b + a & c

   | Comm | Assoc | Dist
 * | NO   | YES   |     
 + | YES  | YES   | *    
 & | YES  | YES   | + *

The user will input an expression, the syntax of the input expression is called "input form". It has the following grammar:

inputform ::= expr
var ::= [a-z] // one lowercase alphabet
expr ::= add
       | add & expr
add ::= mult
      | mult + add
mult ::= prim
       | prim * mult
       | prim mult
prim ::= var
       | ( expr )

Before That means, the order of operations is * + &, a + b * c & d + e = (a + (b * c)) & (d + e) Furthermore, the operator * can be omitted: a b (c + d) = ab(c + d) = a * b * (c + d)

Whitespace is stripped out before parsing.

Examples:

(a + b) * (c + d)
= (a + b)(c + d)
= (a + b)c + (a + b)d
= ac + bc + ad + bd
(a & b)(c & d)
= ac & ad & bc & bd
(a & b) + (c & d)
= a + c & a + d & b + c & b + d
((a & b) + c)(d + e)
= ((a & b) + c)d + ((a & b) + c)e (I'm choosing the reduction order that is shortest, but you don't need to)
= ((a & b)d + cd) + ((a & b)e + ce)
= ((ad & bd) + cd) + ((ae & be) + ce)
= (ad + cd & bd + cd) + (ae + ce & be + ce)
= ad + cd + ae + ce & ad + cd + be + ce & bd + cd + ae + ce & bd + cd + be + ce

Due to commutativity, order of some terms do not matter.

Your program will read an expression in input form, and expand the expression fully, and output the expanded expression in input form, with one space separating operators, and no spaces for multiplication. (a + bc instead of a+b * c or a + b * c or a + b c)

The fully expanded form can be written without any parens, for example, a + b & a + c is fully expanded, because it has no parens, and a(b + c) is not.

Here is an example interactive session (notice the whitespaces in input)

$ expand
> a(b + c&d)
ab + ac & ab + ad
> x y * (wz)
xywz
> x-y+1
Syntax error
> c(a +b
Syntax error

So the basic problem is to find all the equivalent expressions allowed by the commutation, association and distribution rules? Or is it supposed to only display the most expanded form?

rmckenzie · Answer 12 · 2011-06-17 03:47:51Z

The Game of Life

John Horton Conway's simulator The Game of Life is a very simple array-based program which simulates mono-cellular life via four simple rules.

Any True cell with fewer than two True neighbors "dies" (becomes False), as if caused by under-population.
Any True cell with two or three True neighbors "lives on" to the next generation.
Any True cell with more than three True neighbours becomes False, as if by overcrowding.
Any False cell with exactly three True neighbours becomes a True cell, as if by reproduction.

Your task, should you choose to accept it, is to golf an implementation of this simple game which adheres to the following specs.

Input

The game's initial state is entered via STDIN, with lines of this format

x,y\n

where x,y is a point with an initial Boolean value of 1 or True.

Entries should take the following input via argv

$ ./foo.bar X_size Y_size Itters

X_size is the world's X space [0,X_size-1]
Y_size is the world's Y space [0,Y_size-1]

*All game activity will take place in the rectangle (0,0) (X_max,Y_max)*

Itters is the number of clock ticks the simulation should pass before printing the world

Output

The output will be of the same format as the STDIN input, a newline-delimited list of points which are "True" at the end of the simulation.

NOTE: the order in which the points are printed is irrelevant.

Test Cases

Case 1
Input: $./foo.bar 3 3 2
     1,0
     1,1
     1,2
Output:
     1,0
     1,1
     1,2

Case 2
Input: $./foo.bar 6 6 1
     1,3
     1,4
     2,4
     3,1
     4,1
     4,2
Output:
     1,3
     1,4
     2,4
     3,1
     4,1
     4,2
     3,2
     2,3

<dmckee> Related: stackoverflow.com/questions/3499538/… </dmckee>

Alexandru · Answer 13 · 2011-06-21 22:21:43Z

up vote 1 down vote

Perfect Hash Generator

Given N words you are to generate a perfect hash function (ala gperf). A perfect hash function for a set of strings is a hash function with no collisions. An additional condition is that the range of the generated hash function must be [0...O(N)] (i.e. at most a constant times larger than N). You can use any language for the generated function.

answered Jun 21 '11 at 22:21

community wiki

Alexandru

Sounds good at first blush. Do you foresee this as a [code-golf] or some more extensive challenge? If the later what metric would be used to judge it? I think that evaluation of results for compliance is easy enough if the resulting hashes are composed into programs---in unix: entry < testfile > hash_program && hash_program < testfile | sort -u | wc -l and compare to wc -l testfile---but less obvious if the submitters don't provide a scaffold (and if they do should it be counted toward length in the event that this is a [code-golf]?). – dmckee♦ Jun 22 '11 at 1:24

boothby · Answer 14 · 2011-07-06 23:55:45Z

Metagolf: Catlike Piet

The goal of this is to write a catlike program, which would be executed (in a Unix environment, though you needn't stick to that) by the following:

yourprogram < file > output
piet output

where piet output writes the contents of file to stdout. That is, you're to generate a Piet program which prints the input to yourprogram.

One-liners

Straight line programs can be written in Piet... in straight lines. If you're willing to take a hit to your score, your output can take the form of a string of commands:

=  none (continue color block)
|  push
^  pop
+  add
-  subtract
*  multiply
/  divide
%  mod
~  not
>  greater
.  pointer
\  switch
:  duplicate
@  roll
$  input number
?  input character
#  output number
!  output character

which is trivial to convert to a Piet program with the following (partially golfed) Python code:

def P(s):
 h=v=0;l=len(s)+1;R="P3 %i 2 255 192 0 0 "%(l+2)
 C=[1,3,2,6,4,5];V=[0,192,192,255,0,255]
 for x in map("=|^+-*/%~>.,:@$?#!".find,s):
  C=C[x//3:]+C[:x//3];V=V[x%3*2:]+V[:x%3*2]
  for i in [1,2,4]:R+="%i "%V[(C[0]//i)%2]
 return R+"255 "*4+"0 0 "+"255 "*l*3+"255 0 0 "*2

The dimension of said program is (n+3) x 2 if there are n characters in the string.

Scoring

Your code will be judged on the maximum dimension of the images that it outputs.

Part 1: Take the maximum score taken over all ascii codes (that is, single-character inputs), discounting EOF.
Part 2: Take the score for the input "Hello. My name is Inigo Montoya. You killed my father. Prepare to die."

Your score is the product of the scores in part 1 and part 2.

Punishment: Double your score if you write one-liners as above (that is, if you don't output an image).

Bonus: If your program is written in Piet, take the square root of your score above.

It took me a while to understand the task as "Write a program taking INPUT which produces as output a piet program that takes no input but produces INPUT." I think it is a interesting and challenging, but it's reception will depend entirely on how many people are willing to learn/futz-around-in/deal-with piet. And I have no feel for how many that is.
@dmckee; would it be better if I just used a reduced instruction set, and only ask for the instruction stream? I think this is still challenging with {push 1,duplicate,add,subtract,multiply,output}. Come to think of it, if I restrict to {push 1,duplicate,add,output}, there's a reduction to some awesome algorithms.
I did this in piet some time ago: craigoclock.blogspot.com/2011/05/metaprogramming-in-piet.html

2 revs Keith Randall · Answer 15 · 2011-07-26 01:44:25Z

Lazy JavaDoc [posted]

I'm too lazy to write a JavaDoc comment myself, there's a lot of typing and it is mostly boilerplate. Write a program to generate a JavaDoc comment with $ as a placeholder for the actual descriptions given a method specification.

Example input:

Integer method(int arg1, String arg2) throws InvalidArgumentException, NullPointerException

Example output:

/**
    $
@param arg1 $
@param arg2 $
@return $
@throws InvalidArgumentException $
@throws NullPointerException $
*/

Some notes:

There won't be any static, private, or other qualifier on the method, just the return type.
There should be no @return tag if the return type is void.
It is possible that there will be no throws clause.
You should accept the one-line method spec on stdin and write the result to stdout.

And there is the possible followup question, generate HTML given a filled in javadoc comment and a method spec.

"There may not be any" can be read two ways. I'd suggest instead "It is possible that there won't be any".
Do we need to check types for validity? And if so, what types are valid?

4 revs, 2 users 99% Gareth · Answer 16 · 2011-08-10 17:12:50Z

up vote 1 down vote

Wordsearch solver [Posted]

edited Aug 10 '11 at 17:12

community wiki

4 revs, 2 users 99%
Gareth

	Looks good to me, as a bonus any working solution plus `diff` add up to a validator. – dmckee♦ Aug 3 '11 at 22:09
	What's the correct behaviour if a word occurs twice? – Peter Taylor Aug 4 '11 at 8:38
	@Peter I was going to say that that would not be the case before I realised that one of the examples had that exact problem! I've altered that example, so you can assume that will only be one occurrence of any listed word in the wordsearch. – Gareth Aug 4 '11 at 9:39
	I've altered the question as well, since tightening up questions is part of the point of posting them here. – Peter Taylor Aug 4 '11 at 9:51
	@Peter Thanks.. – Gareth Aug 4 '11 at 9:57

5 revs Gareth · Answer 17 · 2011-08-27 09:52:17Z

up vote 1 down vote

What comes next? [Posted]

edited Aug 27 '11 at 9:52

community wiki

5 revs
Gareth

This question may need a bit of work... – Gareth Aug 11 '11 at 10:43

1

I like the idea, but practically how would one be able to solve such a problem in any reasonable length? Most commercial software which does this sort of thing has specific routines for linear, exponential and power functions. were the nth item calculable by some f(n-1) or f(n) it would be possible to use techniques like linear regression and tangent-line approximation to guess at the next number in the sequence or reverse-engineer the f(x). For most golfs, easy is the key to drawing answers because many posters just don't have the time to invest in longer/harder problems. – rmckenzie Aug 15 '11 at 23:55

@rmckenzie Thanks for your commment, I was wondering for while if anyone was going to say anything at all. :-) I understand the need to make problems easy enough to solve in a spare half an hour or so, while making sure they're not totally trivial, and I think I've done ok so far - though others may disagree. I'm still not sure I've explained myself properly in this problem, because I've just implemented a solution to it (not golfed) in 42 lines of Scala which took about an hour. – Gareth Aug 17 '11 at 11:11

lol I feel you on getting no traffic... my only real gripe about this site. Could I take a look at your solution? I think I could help you firm up the spec some by looking at what YOU tried to solve. – rmckenzie Aug 17 '11 at 22:06

@rmckenzie I've added my solution to the question. – Gareth Aug 18 '11 at 8:10

Looking at it again, I think the task seems intimidating at first, but it's actually not as bad. Given that there are only at most 4 options per step. Assuming that all calculations involve integers, sometimes there are as few as 2. I have an idea that I'm going to try out right now to see how feasible it is. – migimaru Aug 18 '11 at 12:46

@migimaru Yes, I think that I may need to point out that only one of +,-,* or / are available at each step earlier in the question to avoid scaring people away. – Gareth Aug 18 '11 at 13:00

@Gareth Yeah, it's certainly doable once you get an approach in mind. I just whipped up a Ruby solution at 499 characters ungolfed. – migimaru Aug 18 '11 at 13:31

Although implied, it would be a good idea to guarantee in the spec that any sequence will repeat two or more times. This ensures that any input must be solvable because you won't have a sequence occur 2.5 times or something stupid. Looking at your solution, I think this is actually a very reasonable question. – rmckenzie Aug 18 '11 at 14:24

@rmckenzie I have a section -

The repeating sequence length will never be more than half the length of the list of integers, so that you have the sequence repeating at least once for confirmation.

- which is supposed to cover that, I take it that it's not really clear enough? Also, a sequence could repeat 2 and a half times - my last example finishes before the -4 which the program should be able to handle. I'll edit the question to try and be clearer. – Gareth Aug 18 '11 at 14:34

Beg pardon, didn't see that section. I would suggest front-loading your spec and closing with examples. Otherwise I (and maybe it's just me) just see test-cases and my eyes glaze over. I suppose there's no reason to gurantee an integer number of repetitions, but it would allow for more concise/simpler solutions. Consider - if a whole number of repetitions were ensured one could factor the length of the input array just to give the program an idea of how long the sequence is. Maybe I'm just seeing a speedup that doesn't help golfs due to length, but there it is. Your question, your rules. – rmckenzie Aug 18 '11 at 14:42

I think allowing a non-integer number of repetitions makes it a lot more interesting, even if it makes the code longer. – migimaru Aug 18 '11 at 15:00

@rmckenzie I think I prefer the question with the partial sequences in - maybe I could put a limit on the length of the sequence (10 operations, say)? – Gareth Aug 18 '11 at 15:04

Capping the length of the sequences would also work.. as long as there is a minimum sequence occurrance of 2 non-integer cases will have definite solutions and now that I've got my writer's cap on I like the idea. – rmckenzie Aug 18 '11 at 15:18

@rmckenzie Okay, I'll put the 10 operation limit in the question. – Gareth Aug 18 '11 at 15:25

3 revs migimaru · Answer 18 · 2011-08-28 10:44:27Z

up vote 1 down vote

Arithmetic Golf: Reach 2011 [Posted]

edited Aug 28 '11 at 10:44

community wiki

3 revs
migimaru

	The underling problem is easily specified as an iterative deepening search on a quad tree, so some languages may make this very easy unless you make at least on of the test inputs hard enough that a exhaustive search becomes very long indeed. – dmckee♦ Aug 18 '11 at 15:38
	Can you explain that a bit more, or provide some links for reference? I'm not familiar with quad trees. – migimaru Aug 18 '11 at 15:43
	Quad tree--like a binary tree but four children per node. There are only four choices at each new digit, so I can expand all possible combinations fairly cheaply (it only goes as 4^N, after all). For instance your 10 digit run requires 2^20 ~= 1,000,000 nodes in the tree. Allow 8 bytes per node and we're talking a whole 8 MB of RAM. No problem on a modern machine (or even a smart phone) – dmckee♦ Aug 18 '11 at 16:05
	You can seek a input that need about 15 digits to make exhaustive search impractical. Alternately adding another operation or two will cause the tree to blow up faster (with six operations 10 digits would imply 8 GB needed for the exhaustive search). – dmckee♦ Aug 18 '11 at 16:07
	Hmm... If there were a 5th operation, say exponentiation, does that reduce the effectiveness of using a quad tree much? Or would it be better to change the rules and allow taking 1-2 digits as the next operand? – migimaru Aug 18 '11 at 16:12
	Well, you have to use a five-branching tree (quint-tree? pente-tree?), and the size grows that much faster. – dmckee♦ Aug 18 '11 at 16:14
	Sorry, my computer was lagging under some test code so I didn't see your comment before I posted that. So it looks like adding more operations is an option. Is it also feasible to limit the number of digits that the code can "look ahead"? – migimaru Aug 18 '11 at 16:19
	I just had an idea that could make this even more interesting, though it will require more time investment from participants. Instead of a string of digits, I could provide a 2-d grid of digits, and programs would have the option of stepping in any direction without reusing any specific digit. What do you think? – migimaru Aug 18 '11 at 17:38
	That drives the combinatorial complexity of an exhaustive search sky high, and ought to encourage more creative solutions. – dmckee♦ Aug 18 '11 at 17:49
	Is this better? And is 18 holes too many? Maybe it should be a shorter course. – migimaru Aug 19 '11 at 14:03

7 revs Gareth · Answer 19 · 2011-08-29 17:44:54Z

up vote 1 down vote

A Mere Bagatelle [Posted]

edited Aug 29 '11 at 17:44

community wiki

7 revs
Gareth

	Spec says that the first and last rows will always be empty. Examples have the first row non-empty. Otherwise looks ok, a bit straightforward but they don't all have to be mind-benders. – Peter Taylor Aug 27 '11 at 10:26
	@Peter Thanks, I'll edit. – Gareth Aug 27 '11 at 10:36
	Sorry, just realised that the scores in the examples are wrong too. In the first example they all fall to an edge and score 0. In the second example two of them score 0 and the other 8 score 9 each for a total of 72. – Peter Taylor Aug 27 '11 at 11:18
	@Peter Thanks, I've corrected those now. I put in one too many `` on the first example. – Gareth Aug 27 '11 at 11:24
	There should be a slash in there, but it seems to have escaped (pun intended ;-) – Gareth Aug 27 '11 at 11:31
	Maybe worth mentioning whether or not `//` and `\\` should be supported, and if should be then give a test case. – Peter Taylor Aug 27 '11 at 12:56
	@Peter Not sure how `//` or the opposite would be handled or if they even make sense in this game. I'll exclude them. – Gareth Aug 27 '11 at 14:26
	They could work as specified already (I've knocked up a solution), but it's something which could catch people out. – Peter Taylor Aug 27 '11 at 15:00
	@Peter So, they'd move the ball over two columns? Or just the one (the ball presumably slipping between them)? I've just finished my attempt at it and you're right - it is straightforward. The competition here would be to golf it to the max I suppose. Got to go and move some furniture, I'll consider the change when I get back. – Gareth Aug 27 '11 at 15:06

migimaru · Answer 20 · 2011-08-30 14:14:32Z

up vote 1 down vote

Optimal Othello/Reversi Move [Posted]

edited Aug 30 '11 at 14:14

community wiki

migimaru

Looks non-trivial and I can't see any holes in the spec. – Peter Taylor Aug 29 '11 at 8:45

Alexandru · Answer 21 · 2011-06-22 10:07:13Z

up vote 0 down vote

I have another question:

You are given an encrypted English text. Write a program to decrypt it.

I will include a large encrypted text as an example, but the answers must decrypt any text encrypted with the same algorithm, but possible different key. I am still looking which breakable encryption algorithm is suitable for CG. For now I have Playfair.

answered Jun 22 '11 at 10:07

community wiki

Alexandru

Related: Decryption by pattern analysis, Decipher a Vigenère ciphertext. – dmckee♦ Jun 22 '11 at 14:09

Damn. It is so hard to find CG ideas. – Alexandru Jun 22 '11 at 14:46

1

I'm not sure those are identical, I just thought you should see them so that you could figure out how your was going to be different. You will need to be pretty clear in your specification, and pick a cipher with different cryptanalytic properties. – dmckee♦ Jun 22 '11 at 14:52

See also codegolf.stackexchange.com/questions/265/…. Just a simple substitution cipher, and it was pretty hard. – Keith Randall Jul 7 '11 at 4:56

3 revs Alexandru · Answer 22 · 2011-06-22 15:08:56Z

Given a text, determine the language it is written in. The possible languages are: English, Danish, Romanian and Hungarian. The shortest program wins.

Some examples of text in each language can be found at Project Gutenberg

English http://www.gutenberg.org/cache/epub/2600/pg2600.txt
Danish http://www.gutenberg.org/cache/epub/12167/pg12167.txt
Romanian http://www.gutenberg.org/files/11756/11756-0.txt
Hungarian http://www.gutenberg.org/files/30163/30163-0.txt

You are required to include examples of runs on text files other than the ones provided here.

The input file name is given as a command line argument. Except the input text, you are not allowed read additional files (e.g. to train your program) so please encode any data in your program.

Your program must output on of the following words English, Danish, Romanian, Hungarian.

Examples

$ ./language pg2600.txt
English
$ ./langauge pg12167.txt
Danish
$ ./language 11756-0.txt
Romanian
$ ./language 30163-0.txt
Hungarian

Another source of plain text passages might be the Gutenburg project. They do have books in languages other than English.
Thanks. I updated the text problem to include some books from Gutenberg.

migimaru · Answer 23 · 2011-08-17 12:04:26Z

up vote 0 down vote

Choose Your Own Adventure [Posted]

edited Aug 17 '11 at 12:04

community wiki

migimaru

asked	2 years ago
viewed	1259 times
active	1 year ago

Proposed questions (sandbox) Mk II (retired)

This Sandbox is being retired in favor of the newer model

23 Answers

A minimal implementation of the make (1) utility.

Sample Input

Sample output

Facial Recognition [Posted]

Code Golf: Code 39 Barcode Scanner (Posted)

Jump and run [Posted]

Mate in one [Posted]

BlackJack Part II

Rules

Dealing and Bot Moves

Programmer's Interface and Legal Moves

Winner Selection

Code Review github

Issues & ToDo

Version History

Number-Hopper Maze

Egyptian Pyramids [Posted]

Example I

Example II

Example III

Self-Golfing Code

Generate a Texting Dictionary

Inputs

Output

Test Case and Validation

Tags

Expanding Expressions [Posted]

The Game of Life

Test Cases

Metagolf: Catlike Piet

Lazy JavaDoc [posted]

Wordsearch solver [Posted]

What comes next? [Posted]

Arithmetic Golf: Reach 2011 [Posted]

A Mere Bagatelle [Posted]

Optimal Othello/Reversi Move [Posted]

Choose Your Own Adventure [Posted]

You must log in to answer this question.

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

Welcome!

Visit Chat

Linked

Related