Sandbox for Proposed Challenges

Question

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

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

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

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

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

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Answer 1

Access a file when you are at some unknown depth in the directory tree

You have to specify an existing file or directory, like, say,

cat ../../../../../someproject/foo/bar/baz.txt

in bash, or

classpath fileTree(dir: '../../../../../someproject/foo/bar/baz', include: ['*.jar'])

in gradle. The bad news is that your code works together with generated code, and the directory where your code executes may change. So you really do not know how many of these ../ you need.

We want something like ..*/someproject/foo/bar/baz.txt where ..*/ means "the nearest ancestor directory where the following name(s) exist".

Requirements

1. Write a piece of code that lets your language of choice access an existing file or directory using a path that does not specify how many times one must go to the parent directory. "Access" means: read an existing file or list files in an existing directory. "Piece of code" means that it must be possible to use your piece of code in a bigger script (a bigger program).
2. If the specified path exists in multiple ancestor directories, the nearest ancestor is chosen, e.g. ../someproject/foo/bar/baz is preferred to ../../someproject/foo/bar/baz.
3. Report an error if the file is not found. It may be something like "no $dirname", but if your language of choice outputs a lot of information, you probably can use something shorter, provided that it is clear that there is no file or directory and what name caused the problem.
4. There must be no confusing messages, e.g. the user must not see "array index out of bounds" if some file does not exist.

At your discretion

1. Whether you check for existence of someproject/foo/bar/baz or just someproject (that is, you may check for the first directory or for the whole path).
2. The syntax that you use. It may be or not be a function call. It may be an operator, it may be a special kind of literal, whatever.
3. The "nearest ancestor directory" feature is supposed to be used in some script, so it is ok to stop execution of the program when an error occurs. How you signal an error is up to you. It may be throw new IllegalSomethingException("no "+path) as in Java, or die "no $f" as in Perl.
4. Input may be a built-in string object, but need not be a built-in string. Input may be, but need not be, a built-in path object. Your language may (or may not) have access to the source and parse the input.
5. There is no requirement to use the ..*/ notation, although IMO bash and other scripting languages would benefit if they had it. Another candidate for ancestor access syntax is ..., which BTW is a valid file name.
6. Can ..*/ be in the middle of the path? Can ..*/ be used multiple times? Yes and yes, but neither is required. In practice, this may happen only if you concatenate paths. Probably, this will be a requirement in some other contest. In this contest, you have to locate a file-or-directory from one of the ancestor directories.
7. It is not necessary to use only one language, for example, a bash/shell utility may be implemented in C.

Who wins

The shortest solution wins.

Please post your solutions in both "golfed" (shortest possible) and "ungolfed" (layouted and human-readable) variants.

Counting required whitespace

See this post.

Count the code as posted. If there is unnecessary whitespace, remove it. Newlines count as one character (\n), unless your code only works with \r\n. Tabs also count as one character (\t), if your language allows them.

How the length of solution is counted

Considerations:

1. The "some ancestor" functionality is meaningful only in the context of a bigger script, an we want to take this into account.
2. It's evident that both the definition and the usage have some length. We want to take both of them into account.

For the purpose of counting the solution length, we assume that there is 1 (only one) usage, and that there are 5 (five) double-dots ../ in the traditional path: ../../../../../someproject/foo/bar/baz.

The solution length formula is

L = length(definition) + length(usage) - length(usage_without_definition)

In theory, this number may be negative. For example, if your special version of bash already lets you write cat ..*/someproject/foo/bar/baz.txt instead of cat ../../../../../someproject/foo/bar/baz.txt, your solution takes -11 (minus eleven) symbols. But if you first have to teach your bash how to react on ..*, that code also counts.

Example

(The language does not really exist and the code does not work.)

Language: Gloomy DSL for Gradle

Definition:

def mypath(s) {
    apply_magic s
}

Definition without whitespace (28 bytes):

def mypath(s){apply_magic s}

Usage without definition:

buildscript {
    dependencies{
        classpath fileTree(dir: '../../../../../someproject/foo/bar/baz', include: ['*.jar'])
    }
}

Usage with definition:

buildscript {
    dependencies{
        classpath fileTree(dir: mypath('..*/someproject/foo/bar/baz'), include: ['*.jar'])
    }
}

Comparing usages:

classpath fileTree(dir: '../../../../../someproject/foo/bar/baz', include: ['*.jar'])
classpath fileTree(dir: mypath('..*/someproject/foo/bar/baz'), include: ['*.jar'])

The new usage is 3 characters shorter.

Usage + definition:

buildscript {
    def mypath(s){apply_magic s}
    dependencies{
        classpath fileTree(dir: mypath('..*/someproject/foo/bar/baz'), include: ['*.jar'])
    }
}

L = -3 + 28 = 25

Answer 2

Merge sort with NaN

Merge sort is a sorting method using the follow steps:

1. Divide input into lists, each containing exactly 1 element.
2. Merge each pair of lists, leaving the last one alone if there are odd amount of lists
3. Repeat 2 until only one list remain.

The merge subroutine is as follow:

1. Let output be empty list
2. Move the smaller element of beginning of two input list to end of output, from second list¹ if equal.
3. Repeat 2 until one of the input is empty
4. Move elements in the other input to end of output.

This usually works fine, until NaN exist in input. Comparison would say NaN equals to every number², which may result in unintended result.

Given a list, decide if it's possibly an output of merge sort.

Test Cases

[2,3,1] => false    # No NaN, can't be unordered
[2,NaN,1] => true   # [[1],[NaN],[2]] => [[NaN,1],[2]] => [[2,NaN,1]]

To allow more languages to answer, you can assume all inputs are positive integers or NaN, and use non positive integer to mean NaN instead.

Shortest code win

^{1 Usually it's coded as something like *d++=*a<*b?*a++:*b++
2 If both a<b and b<a are false, comparison would treat them equal}

Sandbox Note

• Suggested test cases?

Answer 3

Sum of numbers in a rectangle

Answer 4

Miracle Miracle Octad Generator Generator

Answer 5

Round a number badly

In this challenge, you are going to round a number badly!

Round a number badly?

Oh, you don’t know how to do that? Let me explain:

Let’s assume the number has \$n\$ decimal places. You need to:

1. Round the number to \$n-1\$ decimal places.
2. Round the previous number to \$n-2\$ decimal places.
3. Round the previous number to \$n-3\$ decimal places.
4. And so on, until you end up rounding to \$0\$ decimal places (the nearest integer). Output this final number.

(0.5 rounds up to 1)

What’s so special about it?

It’s mostly like normal rounding:

2.33 -> 2
3.55 -> 4
6.5  -> 7
3.0  -> 3
8.44 -> 8

But it isn’t in some cases:

3.45       -> 4
6.446      -> 7
8.44444447 -> 9

Input, Code, Output

Everything follows standard CG&CC guidelines.

Objective

It’s code-golf of course, so shortest answer wins!

---

code-golfmathematics

---

Questions

• Is the challenge clear enough?
• Is it a duplicate?
• Are there any tags I missed?
• Anything else?

Answer 6

Complement of a set of ranges

Consider a shop that exists for a given range of time. At certain times during the shop's existence items can go on sale. These items will be on sale for at least one unit of time.

Challenge

Given such a shop, and the times it has items for sale, find the non-overlapping ranges of time when the shop is not selling anything.

Your inputs will be:

• A two-length array that represents the range of time the shop exists for.
• A set, where each element is a two-length array that represents a range of time that an item was on sale for.

Your output will be:

• A set, where each element is a two-length array that represents a range of time that no item was on sale for. Where no element's range should overlap another's range (see specifics).

All values defining a time range will consist of positive integers (or zero).

Example

A shop exists for the time range [0, 10].

An item is put up for sale during the time range [2, 3]. Another item is put up for sale during the time range [4, 6]. Another item is put up for sale during the time range [5, 8].

So, there are no items on sale from times 0 to 2, 3 to 4, and 8 to 10.

Inputs: [0, 10] and {[5, 8], [2, 3], [4, 6]}

Output: {[0, 2], [3, 4], [8, 10]}

Specifics

The two inputs may be taken in any order, and utilise any formatting/style convenient. Similarly, the order within the output, and its format, is flexible. Just ensure it is clear how it should be interpreted.

e.g., input and output for the above example could be encoded as:

Inputs: 0,10,5,8,2,3,4,6

Outputs: 3,4,8,10,0,2

You may assume that the input time ranges overlap on a common boundary. i.e., items on sale for [1, 3] and [3, 4] is effectively a sale for [1, 4].

No time range (input or output) should span less than one unit of time: i.e., [1, 1] or [7, 7] is not permitted.

So that the concept of 'overlapping' time ranges is well-defined, consider a function overlaps which takes two time ranges and determines whether they overlap or not (true/false). Then the following statement holds true:

$$overlaps([a, b], [c, d]) \iff (c\geq a \land c\leq b) \lor (a\geq c \land a\leq d)$$

You may use any logically equivalent definition.

Test cases

(first input is the time for which the shop exists, second is the times for which items were on sale)

[0, 100] {[3, 7], [2, 5], [17, 54], [99, 100]} -> {[0, 2], [7, 17], [54, 99]}

[7, 20] {[8, 17], [12, 13], [14, 17], [9, 16], [18, 19]} -> {[7, 8], [17, 18], [19, 20]}

[1, 2] {[1, 2]} -> {}

code-golf

Answer 7

Complete a Mystery Sequence II

This is an expanded version of nyxbird's challege.

Challenge

Given a sequence of three non-negative integers, determine the type of the sequence - whether it is arithmetic, geometric, part of the Fibonacci sequence, or part of the triangular numbers sequence. Output the fourth term of the sequence.

Test cases

// Arithmetic
(0, 1, 2) -> 3
(2, 3, 4) -> 5
(10, 15, 20) -> 25
(11, 11, 11) -> 11 // could be considered geometric, output is still 11

// Geometric
(2, 4, 8) -> 16
(1, 3, 9) -> 27
(1, 2, 4) -> 8

// Fibonacci
(21, 34, 55) -> 89
(0, 1, 1) -> 2
(2, 3, 5) -> 8

// Triangular
(15, 21, 28) -> 36
(0, 1, 3) -> 6
(1, 3, 6) -> 10 

Answer 8

Test for Irreducible Complexity (Check for Redundant Characters)

I may need some additional help coming up with the full spec for this competition. As of right now, this is just a concept.

Many interesting questions, such as the "42" question in this sandbox, involve finding the longest program which is not reducible. This means that no set of characters can be removed and still allow the program to function as desired.

The basic idea is that your program will test a Base Program to make sure that it contains no redundant characters. The input will consist of:

• Base Program (in the same language as your answer)
• Expected Output

Your program will simply evaluate all possible subsequences of the Base Program and verify that none of them give the Expected Output.

This challenge actually has a utility value to several other challenges. For example, it verifies the results of a "longest non-reducible"-type challenge. In addition, it could make sure that a golfed solution cannot be golfed further.

I assume that the winning criteria will be fastest program, as cycling through all the possibilities takes a long time.

Problems

A sequence of length N has 2^N subsequences. Even if each evaluation is done very quickly, it might be unfeasible to test any program with more than 20 or so characters in a reasonable amount of time.

Answer 9

code-golf regular-expression generation string

Wordlist detector

You are to write a program which, given a list of words, constructs a regular expression to match all these words but nothing else. Both your program and the constructed regular expressions are to be as short as possible.

Input and Output

Input comes on standard input and consists of one line giving n, the total number of words, followed by n lines with one word each. The number of words will be less than 1000, the length of each word less than 30. Words will consist only of lower case ASCII letters, i.e. a-z. You may choose to ignore the first line and use EOF instead to end the list.

Output shall be written to standard output. It consists of a single line, giving a POSIX extended regular expression to match these words and no others. Since input for this regex is not restricted to letters only, elements like . or [^…] won't make too much sense, which limits the language in a natural way. You may choose whether you want to terminate the line with a newline or not. Programs may choose to print multiple lines of output, in which case only the last one will be used for scoring. So you might print intermediate results and continue searching for improvements.

Test cases

Each submission may be accompanied by one regular expression. When scoring the submissions, I'll use this regular expression to reconstruct a word list from it. The code to do this reconstruction can be found at the end of this post. The reconstructed word list must fit the input specification above in terms of word count and length. It would be nice if your own program would be able to regenerate that regular expression from the word list, but that is not a strict requirement. But please don't paste bogus programs just to submit a challenging regular expression, though.

These test cases will be collected and fed to all programs for scoring.

Scoring

The final score of each program will be the program size plus the size of all its generated regular expressions for the inputs collected from submitted answers, including the example from this question. So short code which produces too long results might get beaten by longer code which generates shorter expressions.

Does this still qualify as code-golf?

Submissions which generate an incorrect regular expression for one of the test cases will be disqualified, as will those which don't terminate in the allotted time. You can use the input reconstruction program below to check whether a produced regular expression does encode the correct word list.

Requirements

All submissions are welcome, but in order to include your submission in the tournament, it must be executable with reasonable effort on my Linux machine. It shouldn't depend on any exotic libraries, or any specialized ones which take too much work away from your own program. It must operate in reasonable time, say no more than five minutes per input. Your output must be reproducible, so if you use randomization at some point, please seed the randomizer, and please don't terminate an improove loop by a timer measuring execution time or some such.

Tournament times

I'll run the first major tournament two weeks after posting this question. I'll include a table of the results in this question. I'll try to run tournaments repeatedly as late submissions arrive, but I'll not promise any regular schedule.

Example

An very simple example application would be in Python 3 (53 chars):

print('|'.join(input() for i in range(int(input()))))

And here is a test case which could be posted along with the program, although this program obviously doesn't generate exactly this concise output:

bann?ana|ap(fel|ple)|s[ou]n|[hs](a|ou)nd

The expansion of that expression could be turned into the following example input, which need not be posted as part of an answer since it can be deduced from the regular expression:

10
banana
bannana
apfel
apple
son
sun
hand
hound
sand
sound

Regex expander program

And here is a program to turn regular expressions into word lists, again written in Python 3.

#!/bin/env python3
concat = set(('',))
altin = set(('',))
altout = set()
prev = None
stack = []
regex = iter(input())
for ch in regex:
    if ch == '(':
        stack.append((concat, altin, altout))
        altin = concat
        altout = set()
        prev = None
    elif ch == ')':
        concat.update(altout)
        prev, altin, altout = stack.pop()
    elif ch == '|':
        altout.update(concat)
        concat = altin
    elif ch == '[':
        ch = regex.__next__()
        cls = []
        while ch != ']':
            if ch == '-':
                crange = range(ord(cls[-1]), ord(regex.__next__()) + 1)
                cls.extend(map(chr, crange))
            else:
                cls.append(ch)
            ch = regex.__next__()
        prev = concat
        concat = set(w + c for w in prev for c in cls)
    elif ch == '?':
        concat.update(prev)
        prev = None
    elif ch >= 'a' and ch <= 'z':
        prev = concat
        concat = set(w + ch for w in prev)
    else:
        raise Exception("Illegal input")
if stack:
    raise Exception("Unclosed group")
concat.update(altout)
words = sorted(concat)
print(len(words))
print('\n'.join(words))

This is restricted to the part of regular expression syntax which I expect for this answer. If you have good reason to use something I did not consider, feel free to do so although I will likely have to update this code to cope with it. If you find a bug, please let me know.

Answer 10

Rhymalator

(at the point, it's just something that came to me before i wake up, so it may need some adjusting, and i'd like some feedback as to if this could be fun)

---

The code challenge is to write a program that takes as input a calculation in Reverse Polish Notation and outputs the result. It must at least implement + - * /. It So far so easy, but to make it fun and "artistic", the following restriction applies:

• The source code must rhyme when read. Example in PHP

  $iterator = str_split($a);
  foreach ($iterator as $key=>$value){
      if ($key > 3){
          ++$virtue;
      }
  }
  

  (the rhyme is on value-virtue)

• Lines whitout readable characters count as whitespace (the two lines with } in the example)

  popularity-contest code-challenge

Answer 11

Implement Kalah code-golf

The game of Kalah is a two-player board game in the Mancala family. Your implementation must:

• Identify the active player ("Player 1" or "Player 2")
• Display board state (in format specified below)
• Accept input to allow that player to move (using index system below)
• Announce a winner ("Player N wins")

Overview

Each player has a line of six spaces, called houses, and one additional space called a store. Each space holds seeds, which move from house to house in a counter-clockwise direction. The objective is to fill your store with seeds.

You must represent the board in the following two-row format with stores offset, where HH is a house and SS is a store:

SS HH HH HH HH HH HH
   HH HH HH HH HH HH SS

The top row represents the number of seeds in player #1's spaces, and the bottom row represents the seeds in player #2's spaces. The S in each row is the respective player's store (player #1's is top-left, #2's is bottom right). Single-digit values should include a leading space.

In this challenge, user-input will identify each house numerically. Use a left-to-right, indexed-from-one scheme for both sides:

S 1 2 3 4 5 6
  1 2 3 4 5 6 S

Note that the players' stores are not numbered, because seeds placed in the store never move out.

Rules

Wikipedia has a good summary of the game and its rules:

1. At the beginning of the game, three seeds are placed in each house.

2. Each player controls the six houses and their seeds on his/her side of the board. His/her score is the number of seeds in the store to his/her right. [Clarification: from our perspective, player 1's store is to the left, player 2's store is to the right.]

3. Players take turns sowing their seeds. On a turn, the player removes all seeds from one of the houses under his/her control. Moving counter-clockwise, the player drops one seed in each house in turn, including the player's own store but not his/her opponent's.

4. If the last sown seed lands in the player's store, the player gets an additional move. There is no limit on the number of moves a player can make in his/her turn.

5. If the last sown seed lands in an empty house owned by the player, and the opposite house contains seeds, both the last seed and the opposite seeds are captured and placed into the player's store. [Clarification: moves that end on an opponent's empty house end normally without a capture.]

6. When one player no longer has any seeds in any of his/her houses, the game ends. The other player moves all remaining seeds to his/her store, and the player with the most seeds in his/her store wins.

Example

(Parenthetical text should not appear in actual output.)

Player 1
 0  3  3  3  3  3  3
    3  3  3  3  3  3  0
> 2                      (prompt arrow and line break
                          are purely optional)
 Player 2
 1  1  0  3  3  3  3
    4  3  3  3  3  3  0
> 4

Player 2  (P2 gets a bonus turn from rule #4)
 1  0  3  3  3  3  3
    4  3  3  0  4  4  1
> 5

Player 1  
 1  0  3  3  3  4  4
    4  3  3  0  0  5  2
> 4

Player 1  (P1 captures P2's seeds in space 1)
 6  0  4  4  0  4  4
    0  3  3  0  0  5  2
...

Player 2
12  0  0 10  0  1  0
    0  0  0  0  0  1 13
 > 6

Player 1 wins            (because the non-finishing players gets
                          all remaining seeds on their side, it's 23-14)

---

Meta question: Would this be improved by removing some of the rules?

Answer 12

[This is the first time I'm using the sandbox. I want to get feedback/suggestions before posting the question.]

Make a spider web (standard, orb type) that fills frame in the ratio of n:m, where n, m are input integers. You may use the example below as a model (but you don't need to use labels).

Your web should have multiple radii, at least 4 of which attach directly to the frame. The remaining radii should attach to the outer outline (perimeter) of the web. The web should have at least 15 radii. The mesh spacing should be more or less uniform spacing (although occasional weaving mistakes" or crossings are encouraged and will receive a bonus).

This is code-golf, so the shortest code (minus bonuses) wins.

---

Bonuses (to be removed from the number of characters in your code). Bonuses are awarded for the following features that reflect the architecture of an actual web (as opposed to a perfectly symmetric rendering). They are somewhat greater than usual as an incentive for attention to detail and realism.

-mesh spiral instead of concentric circles: 40 pts

-assymmetric web: 31 pts. (e.g. height of capture area greater than width)

-irregularly spaced radii: 42 pts

-distinct segments between radii (straight or crooked, but not the arc of a circle): 32 pts

-outer and inner outline clearly distinct from the spiral: 41 pts

-irregular outer outline: 20 pts

-2 or more easily observable reverses in spiral: 40

The accept will be awarded on Feb. 20, 2014.

Answer 13

Write a PHP Code Golfer code-challenge

Since my currently daily programming is in PHP, I tend to try the challenges on the site using that language, but frequently I large program because of the verbosity of the language. And then I have to strip it for presentation...

But this is not a tips question, it's an eviscerating challenge.

The objective is to write a program in the language of your choice that takes a PHP file and outputs a golfed valid PHP file with the same functionality.

The scoring will be the average reduction in percent of the result of running the program with 3 selected files (not yet selected, I was thinking of some open source library)

The output file should run on at least 5.4 (so shorthand arrays, function dereference, traits are available)

Since the score is the difference between the ungolfed and golfed files, techniques beyond minifying are encouraged, such as using code subtitution, eval, compression, $$ (variable variables), dereferencing...

---

Scoring example: The 3 sources have 450, 1200 and 3500 chars respectively

Answer 1
results lenghts: 250, 1000, 3300
reduction: 200, 200, 200 (44%, 17%, 6%) average: 22%

Answer 2
results lenghts: 350, 1050, 3150
reduction: 100, 150, 350 (22%, 13%, 10%) average: 15%

In this case Answer 1 would win, even tough both answers got the same total reduction (-600 chars)

Answer 14

Create diagonal code

Your task is to create a program that outputs d=s*sqrt(2).

Specs:

• Your program must be at least 4 lines long;

• d=s*sqrt(2) cannot be hardcoded as is (so using ascii, compression, encoding, etc. is allowed and encouraged);

• For each line of code n, pick up the nth character. The string obtained this way must be a valid program in a programming language of your choice, that must be different from the one you used for the main program. The obtained program must compile successfully, but it can throw errors, exceptions, etc.;

• If at the nth line there is no nth character, you can consider that character as a whitespace or a newline. This cannot be done for the first 4 lines, which must be long at least n non-whitespace characters.

• Your main program must end successfully (no errors, exceptions, etc.);

• Internet access is forbidden;

• Most upvoted answer in 2 weeks wins.

Happy coding!

popularity-contest

---

I was unsure about making this a code-challenge with several bonuses (polyglot answer, secondary program still valid, etc...).

---

Some bonuses for the code-challenge version:

Your valid answer starts with 0 points. You gain:

+10 if the secondary answer hides a third answer in it;
+15 for any other hidden answer;
+5 for every hidden answer that runs and ends successfully, without any problem;
+10 if your main answer is a polyglot;
+15 for every hidden answer that is a polyglot;

---

Which version would you prefer? Is there something you would change/improve in this question?

I personally like the code-challenge one, but the KISS principle (Keep it simple, stupid!) reminds me that I may be wrong.

Answer 15

Create a Karnaugh-map calculator

Given an input of a truth table, generate a corresponding K-map.

Input:

Input will be of the form 10110001 where each bit is a row of a truth table. Count from the left to the right; so that input would be a table of:

i2i1i0 f
0 0 0|1
0 0 1|0
0 1 0|1
0 1 1|1
1 0 0|0
1 0 1|0
1 1 0|0
1 1 1|1

Max 4 variables will be inputted

K-maps (a small explanation):

K-maps are a way of simplifying boolean-algebra expressions.

Let's say we have 4 variables: a, b, c, d. Let the truth-table be 1110101001111111 (and the columns on the truth table be labeled, from left to right: a, b, c, d). Arrange the variables like so:

   cd
ab\   00 01 11 10
   00
   01
   11
   10

Note the grey-code counting scheme.

Fill in the table with the corresponding values from the truth table:

   cd
ab\   00 01 11 10
   00 1  1  0  1
   01 1  0  0  1
   11 0  1  1  1
   10 1  1  1  1

Group the values in rectangles whose dimensions are the largest possible powers of two. Note that this table signifies a torus, so wrap over the left and right edges.

The expression for the truth table is the ors of the and of the unchanging elements. For this, that would be:

Purple group: ¬b ∧ ¬c (for 0's, make them 1 by notting the value)
Green group: ¬a ∧ ¬d
Black group: a ∧ d
Blue group: b ∧ ¬d

Expression: (¬b ∧ ¬c) ∨ (¬a ∧ ¬d) ∨ (a ∧ d) ∨ (b ∧ ¬d)

Output:

• Generate a 2D K-map (for more variables, add on either side) and show the grouping. K-map must be of the form I used. For less variables, remove rows or columns and change the list on the top left corner.
• assume alphabetical ordering on the variables, that is, the first variable is a, second: b, third: c, and so on.

• Also show the expression. Rather than use the unicode characters, the following is permissible:

  ~ instead of ¬
  * instead of ∧
  + instead of ∨
  

code-golfgraphical-output

---

Edit: Possible duplicate: More fun with gates: Karnaugh simplification

Answer 16

Title: Implement ROT-13... in ROT-13

Content:

Challenge: Implement ROT-13 in code that works as both itself and as the ROT-13 version of itself.

Scoring:

Your score is calculated as a percentage of used, ROT-13 eligible bytes in total of both versions of the program divided by total bytes (all characters) of both versions.

A used, ROT-13 eligible byte is any character that is not part of a comment or ignored by the compiler/interpreter. For example, any character in a brainfuck program that is not +-<>[],. is not considered a used byte, and any character in a C program including and after // or inside /* */ is not considered a used byte. All special symbols in APL are not considered used, as are all characters in a Whitespace program (sorry).

Example scoring:

C: 21/32 = 65.625%

main(){printf("Hello World!");}

Answer 17

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.

Answer 18

With its strange choice of 9 different characters (plus space and newline), the ASCII art version of the FreeBSD logo has always looked to me as if it might be nicely formatted, obfuscated code is some programming language. (Is it?)

 ```                        `
s` `.....---.......--.```   -/
+o   .--`         /y:`      +.
 yo`:.            :o      `+-
  y/               -/`   -o/
 .-                  ::/sy+:.
 /                     `--  /
`:                          :`
`:                          :`
 /                          /
 .-                        -.
  --                      -.
   `:`                  `:`
     .--             `--.
        .---.....----.

Therefore I would like to challenge you to make it one: Either specify minimal changes to an existing programming language or minimal changes to this piece of ASCII art (making the artwork look different or significantly changing the character set used are definitely major changes), so that the logo, as source code generates meaningful output.

This should be a popularity-contest challenge, although I wouldn't mind some way of introducing hard scoring and run this as code-challenge.

Answer 19

King of the Hill Fighting

In this game, a player controls 5 bots that attack the other players 5 bots. Each bot has life points, and has to reduce the other playres lifepoints to zero. This post is program that tests the controllers. It is in literate haskell.

> import Data.Set as S
> import Data.Map as M

Here is the arena:

    D---G
   /|   |\
  B |   | J
 /|\|   |/|\
A | E---H | L
 \|/|   |\|/
  C |   | K
   \|   |/
    F---I
20  12    4
  16    8   0

Positions are denoted by letters

> data Positions = A | B | C | D | E | F | G | H | I | J | K | L deriving (Show, Read, Eq, Ord)

Each player is presented a map in which their side is the one with A. Here is code that will reflect it so each player sees their own view.

> pairFlip = (\(x, y)->[(x,y), (y,x)])
> reflect = M.fromList $ [(A,L), (B,J), (D,G), (C, K), (E, H), (F, I)] >>= pairFlip

Lines denote connections.

> connections=S.fromList $
>   [(A,B), (A,C), (B,D), (C, F), (E, D), (E, F), (D, G), (E, H), (F, I)]
>   >>= pairFlip
>   >>= (\(x,y)->[(x,y), (reflect ! x, reflect ! y)])
> 
> connected x y=(x, y) `S.member` connections

The numbers below are the number of life points of generation that each bot.

> regen = M.fromList $
>   [ (A, 20), (B, 16), (C, 16), (D, 12), (E, 12), (F, 12)
>   , (G, 8), (H, 8), (I, 8), (J, 4), (K, 4), (L, 0)]

Answer 20

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.

Answer 21

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.

Answer 22

Calculate pi using a unique method

Your task is to calculate or approximate pi using the most interesting method you know. Well-known things such as using inverse trig functions (asin, acos, atan) or commonly used convergent series are considered uninteresting.

You may calculate pi to any precision desired, but the more precision you can achieve, the better.

popularity-contest pi

Answer 23

I like trees

...so this is a challenge to make me a tree.

Produce a program called tree which takes a single integer argument, N and draws a randomly-generated tree N levels deep, where level 0 is just the trunk.

• Your program must produce visibly different results for at least N=0..5
• The tree ought to not be symmetrical in any axis.
• The tree should be an image
• Tree(5) should mostly fill dimensions of at least 200w*250h
• I should be able to run your tree from a bash prompt, eg. '$ python tree.py 3'

I also accept ferns.

Optionally your tree may be 3d, iterate forever, be colourful, have leaves at level 5, or be lit according to the time of day. However, this is code-golf, so the smallest file wins.

Tags: code-golf

Answer 24

Implement multi-line lambdas in Python.

Guido van Rossum said it couldn't be done, prove him wrong. Your solution should allow multi-line anonymous functions, like:

>>> f = multilinelamba("hour", """
...     if hour > 20 or hour < 6:
...         print "Good night"
...     else:
...         print "Hello world"
...     """)
>>> f(10)
... 'Hello world'

Your solution should be as close as possible to the behavior of real def or lambda. The actual syntax doesn't matter. E.g. you may choose to pass the code as a string as above, or you may find a way to avoid it. The implementation is also open, you may for example define a function, write a preprocessor, or edit the python source, but keep in mind that the solution should fit in the answer, so the last option probably won't work.

Your solution must allow arbitrary python code inside, except the following which is optional:

• recursive use of the multilinelambda "statement" inside of the multilinelambda
• calling the function recursively, i.e. using f inside the multilinelambda in the above function
• defining classes and
• importing modules (these two might be too hard)

You must also be able to use a multilinelambda as a parameter when calling a function.

You get bonus points:

• If your solution captures outside variables in a closure, like real def does
• For correct handling of exceptions in the multilinelambda. They should display similarly to when using def, and include line number relative to the file.
• For allowing default parameters
• For allowing *args and **kwargs

• If the solution admits any kind of consistent indentation. Two options must be considered:

  • All lines have a common indentation (like in the example above) that can be stipped away.

  • The first line of the body is given on the same line as the multilinelambda statement. In this case, all the remaining lines must be checked for consistency. It makes a difference whether the first line starts a block or not. Example:

    multilinelambda("x", """print "Hello"
                            print "World" """)
    
    multilinelambda("x, y", """if x > y:
                                   print "case 1" 
                               else:
                                   print "case 2"
                            """)
    

  In both cases, I may add or remove the same number of spaces to/from each of the lines following multilinelambda.

---

Any ideas for additional criteria? I personally don't really care much about picking a winner, this is more about tinkering and proving that it can be done. But in any way, more "unit tests" will only benefit the question.

Btw., I asked about this kind of question here on meta.

Answer 25

Foreword: This might have been done before, but I couldn't find any such cases. I think the scoring is quite fair now, and the challenge quite clear, but any criticism is welcome. Only thing I am not sure of (besides maybe a similar question existing) is whether it is rewarding enough to add a single language or whether a 2 byte solution which just runs in two languages is going to win (is that possible?).

The challenge

Write a single piece of code that will only output different deterministic integers depending on the language it has been interpreted as.

Scoring

Length of the code divided by the multiplication of the score of every used language. Esoteric languages have score 2 and production languages have score 3. For example, if you have a code of length 120 which runs in whitespace and javascript this will give a score of 120/(2*3)=20.

Rules

• Versions and forks: Different versions and forks may count as different languages, provided that the output is not determined by the version or similar constants in any way. In other words: <?=intval(phpversion())?> or 1<!--[if IE 8]>1<![endif]--> is not allowed.
• The outputted integer should be the constant and only dependent on the language it is run in.
• Only the most common compiler for a language should be used.
• The code should output nothing besides the integer.
• No two interpretations (languages) of the code may yield the same integer.

• In cases where there is any serious discussions of a language being esoteric, it will be counted as esoteric if no commercial company with at least 50 employees can be pointed to developing it's main product in the discussed language.

  ^ Blame the sandbox for that last crazy over specific rule

Answer 26

Split string of powers of 2

I had this idea while playing 2048; Every single power of 2 is unique, even if it contains another power of 2 as a substring because there are none that consist entirely of powers of 2.

For example, the string "2048409632864" can be split into 2048, 4096, 32, 8, 64 easily enough, but it can also be split into 2, 0, 4, 8, 4, 0963, 2, 8, 6, 4 with a simple left-to-right algorithm, which is incorrect.

So, the challenge is to correctly split these numbers in the shortest byte count possible. Is this a good idea?

Answer 27

A "counting" quine

code-golf and maybe quine. Hopefully codegolf.SE isn't tired of quines and quine-derivatives.

The aim of this golf is simple. Write a family of programs A and a single program B in your language, such that:

• Program A(N) produces the source code of A(N+1) when run, independent of file name, current date, contents of STDIN, or similar external variables.

• Program B, when given the source of A(N) as input, returns N. Input can be via STDIN, function argument, preinitialized single-character string variable, or language's equivalent.

Your score is the sum of the lengths of A(0) and B in bytes. Lowest score wins.

I called it a counting quine, because it is easiest to implement like a quine, except it also counts. The purpose of program B is to potentially allow for non-numeric changes between the programs in A, such as an increasing line of asterisks or something.

Things to consider

Is this too similar to "Program that creates larger versions of itself (quine-variant)?"

Golfscript has a particularly powerful answer to the above question, that could be adapted to this challenge. It seems like it would beat even my best J, which itself is a curt 29 + 10 = 39 bytes. If this question is dissimilar enough to post, are we just going to bite the pillow and let these two duke it out? Is there some kind of restriction that might make this a little harder or more unique?

Alternatively, should this be a popularity-contest? Maybe it would be more fun or interesting not to constrain cleverness by size requirements.

Answer 28

(this isn't quite a duplicate of Water-Bucket problem because that question was ill-posed and apparently abandoned; it's also not a duplicate of 3 and 5 Litre Jug Puzzle because that one was just a single instance, and an instance of a different problem to boot)

die-harder

THE PROBLEM

In commemoration of Leslie Lamport's Turing Award, let's borrow a problem from his TLA+ online hyperbook. There are two versions: "Die Hard" and "Die Harder." "Die Hard" is an instance of the general, "Die Harder" problem. "Die Hard" is the following:

Given an empty jug, jug[0], with capacity 3 gallons; and an empty jug, jug[1], with capacity 5 gallons, deliver exactly 4 gallons of water under the following rules; you may:

1. fill a jug completely, making its current amount equal to its capacity
2. spill a jug completely, making its current amount equal to zero
3. pour into a jug from another, either filling the destination, emptying the source, or both

One solution is to

1. fill jug 1 (amounts are 0, 5)
2. pour jug 1 into jug 0 (amounts are 3, 2)
3. spill jug 0 (amounts are 0, 2)
4. pour jug 1 into jug 0 (amounts are 2, 0)
5. fill jug 1 (amounts are 3, 4)
6. spill jug 0 (amounts are 0, 4)

I believe there are 3 more.

"Die Harder" is the following:

Given an ordered collection of n empty jugs with non-zero, not-necessarily unique capacities c[0], c[1], ..., c[n-1], deliver exactly k gallons of water, which may be spread out over multiple jugs, under the same rules as above.

THE CHALLENGE

Beat my reference Clojure code code for

A: performance, by choice of algorithm or by optimization or both (my algorithm becomes intolerably slow when the number of jugs > 3)

B: clarity (no obfuscators; we want to see your algorithm)

C: elegance

D: brevity

The above expresses the priority of the judging criteria: perf is more important that clarity, which is more important than elegance, which is more important than brevity.

Your code should behave as follows:

Given n, capacities in the form of a bracketed list like [3 5 7] and a target amount k, print t solutions in a form like the following in Clojure syntax, which is a solution for n = 2, capacities = [3 5], k = 4, and t = 2:

({:states
  [{:amount 0, :capacity 3, :id 0} {:amount 4, :capacity 5, :id 1}],
  :trace
  [(fill-jug 0)        (fill-jug 1)       (spill-jug 0)
   (pour-from 0 1)     (spill-jug 0)      (pour-from 0 1)
   (fill-jug 1)        (pour-from 0 1)    (spill-jug 0) ] }
 {:states
  [{:amount 3, :capacity 3, :id 0} {:amount 1, :capacity 5, :id 1}],
  :trace
  [(fill-jug 0)       (pour-from 1 0)     (fill-jug 0)
   (pour-from 1 0)    (spill-jug 1)       (pour-from 1 0)
   (fill-jug 0) ] } )

Each of your t solutions must present the final states of the jugs and a sequence of moves, in order, that achieve the solution. Minor variations to the above format are ok.

Extra credit if your code produces optimal (shortest number of moves, fewest pours, etc.) solutions and you can prove so. You may present proofs in commentary with your code; acceptance of a proof is at our sole discretion, as is judgment of clarity and elegance.

Include instructions for running your code if it's non-obvious (as in, "how exactly do I run this bit of INTERCAL?").

OBSERVATIONS

If the gcd of the capacities does not divide the target amount, the problem has no solution. In your golf, you might check this (my reference code assumes it, instead).

Certain moves, while legal, are trivial, namely:

1. filling a full jug
2. spilling an empty jug
3. pouring from an empty jug
4. pouring into a full jug
5. repeating the last move, whatever it was

In your golf, you may either check for these trivial moves or not.

You might unit-test your code on inputs like the following:

capacities = [3 5 7],    k = any integer from 0 through 15
capacities = [3 5 7 11], k = any integer from 0 through 26

A REFERENCE SOLUTION

You can find a reference solution in Clojure here. It includes unit tests that demonstrate the program at work.

License

Copyright © 2014 die-harder

Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.

Answer 29

I have not put substantial effort into this sandbox post. Since I am unsure(and it's probably not) whether this kind of question is a good fit for this site or not. If somebody reputable mentions that the idea has merit, I'll tune this sandbox up, and try to get it in shape for posting.

Obviously the biggest problem is how do you test the code? And that's the part I'm stuck on. If anyone can think of a way to overcome this please let me know! Anyway, here it is:

Write a program that posts itself as an answer

Your program must establish an http connection to codegolf.stackexchange.com, login, and post an answer to this question.

The answer must be in the form of:

"

[Language]

Code

"

Rules: Cannot read source file, or any resource which is identical to your source file in any way.

Tags: popularity contest, quine

Answer 30

Create an Andy Warhol portrait

Andy Warhol was one of the main figures of the Pop Art. One of his most famous works was a Marylin Monroe picture in nine frames changing the colors, saturation and others aspects of a original pic.

The challenge here is to create a program that takes any photo and emulates the Warhol painting with some caveats:

1. Final image should be compossed of 9 different frames.
2. Final image will be compossed from 3 rows and 3 columns.
3. Final image should be sized 3 times width and 3 times height of the original image.
4. The program should output just one image.
5. The image that the program outputs must be an emulation of Warhol works.
6. You cannot use any built in function that doest by itself the Warholization of the picture neither load or use any external image other than the original. You can use your language methods for changing color, hue, saturation..
7. Program should be deterministic: Any given photo should output the same image every time.

The program should read the image in JPG, BPM or PNG (at your convenience) and output the image in the same format.

The program will be tested with these images:

This is a popularity-contest so the most upvoted answers will win. Nobody restrains you from adding more warholized pictures for winning more votes from the judges.