Sandbox for Proposed Challenges

Question

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Most people include applicable tags in their proposal, so for instance you can search for all king-of-the-hill proposals by merely adding the tag name in quotes to the search query.

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

@guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] — DJMcMayhem♦, Aug 29 '19 at 15:19
Why no featured anymore? Can't we have it auto-added or something? — S.S. Anne, Sep 26 '19 at 15:57
@JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary — caird coinheringaahing, Sep 29 '19 at 13:43

SCB · Accepted Answer · 2016-09-26 04:43:53Z

Handwriting Recognition

code-golf image-processing

The MNIST dataset is a series of handwritten digits used as a standard testbed for machine learning, pattern recognition techniques. Each image is of a single digit, 0-9; as a 28x28 pixel grayscale matrix with values from 0-255.

The challenge is to create a classifier for MNIST that scores an Error Rate of less than [TBD] in the least number of bytes possible.

Your program must take a 28x28 2d array in whatever format is applicable for your language representing a single image. For example, the input for the first digit might be:

[[  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  3, 18, 18, 18,126,136,175, 26,166,255,247,127,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0, 30, 36, 94,154,170,253,253,253,253,253,225,172,253,242,195, 64,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0, 49,238,253,253,253,253,253,253,253,253,251, 93, 82, 82, 56, 39,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0, 18,219,253,253,253,253,253,198,182,247,241,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0, 80,156,107,253,253,205, 11,  0, 43,154,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0, 14,  1,154,253, 90,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,139,253,190,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 11,190,253, 70,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 35,241,225,160,108,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 81,240,253,253,119, 25,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 45,186,253,253,150, 27,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 16, 93,252,253,187,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,249,253,249, 64,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 46,130,183,253,253,207,  2,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 39,148,229,253,253,253,250,182,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 24,114,221,253,253,253,253,201, 78,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0, 23, 66,213,253,253,253,253,198, 81,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0, 18,171,219,253,253,253,253,195, 80,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0, 55,172,226,253,253,253,253,244,133, 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,136,253,253,253,212,135,132, 16,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0]]

Conditions:

This is code golf. The shortest piece of code that meets the criteria wins.
The code must take a provided 28x28 input and attempt to classify it.
Testing will take place on my computer at 12pm AEST on Saturday the . I will run each classifier over a set of 1000 images. To be considered, it must correctly classify [TBD] of them. If I can't get your code to run, it wont be counted, so help with loading the images in your language would be appreciated.
Standard loopholes are not permitted.

Questions for Sandbox

Overall thoughts on the challenge?
Has anything been done like this before? Did it work?
Any ideas on a good cutoff for the classifier? I was thinking around 60% correct. Though was going to have a go at it myself to see what I could reasonably achieve.
Does the testing clause make sense? Is it reasonable? Should I put a limit on the languages?
Since barrier to entry is a bit high (knowing how to get hold of the images, possibly some ML experience), is there anything extra I should do to make it easier to start the challenge.
This is my first suggestion for a challenge, is there anything I'm missing?

I actually found a very similar question from back in 2014 (using MNIST). It had a different scoring system and some slightly different criteria and expectations. Is this still worth it? Is it late enough for others to have another go? — SCB, Sep 26 '16 at 3:36
I don't think it's sufficiently different. If you want to provoke others to have another go, you can do so in the chat or by placing a bounty on the existing question. — Peter Taylor, Sep 26 '16 at 13:44
60% correct is way too leniant; current state-of-the-art techniques on this dataset "easily" reach 99+% of correct classification. — Fatalize, Sep 28 '16 at 11:48
Unrelated, but I would like to congratulate you on submitting the 3000th answer to the Sandbox! (That number includes all deleted submissions.) — PhiNotPi, Sep 28 '16 at 15:12
@Fatalize I was thinking 60% because I wanted the emphasis to be on the code-golfing, not the machine learning. If it's lenient enough I'm hoping someone can figure out some really, really simple way that would just scrape in. All in the spirit of code golf. — SCB, Sep 28 '16 at 23:02
@PeterTaylor I was hoping that the idea of a hard limit would switch the challenge around so it's not focused on building a function that works well, but instead building a very short function that works, barely. In the original a slight improvement in code length that decreased the correct matches would be bad, whereas in this challenge decreasing the code length is always good, as long as you still sit above [TBD] correct images. — SCB, Sep 28 '16 at 23:09

Downgoat · Accepted Answer · 2016-09-27 00:19:32Z

Gif - Jif, Jif - Gif

code-golf

_{The point of this challenge is to (not) settle debate on the pronunciation of "gif"} http://38.media.tumblr.com/11bc6092d29c8c6840f9e10184ca03fd/tumblr_mlksz8SLjn1qz4h3co1_1280.gif

The pronunciation of gif is debated and while it's supposed to be (and should be) pronounced jif, it's still commonly disputed.

In this challenge you will be given a set of words that have a g or j, representing the sound that the word is pronounced with. You'll also get some text in which you have to fix the incorrect spellings of gif.

Because this is the internet and everyone always wrong. It's (not) common courtesy to correct them.

Duty Calls

An example of a wrong pronunciation would be:

There was a gif of a mouse eating a burrito

The wrong spelling of gif? Unacceptable! This must be corrected immediately:

There was a jif (as in jar) of a mouse eating a burrito

Are we done? Nope, you're still wrong.

You're always wrong http://travelsummary.com/wp-content/uploads/2013/03/Im-Right-Youre-Wrong-e1363993322818.jpg

This must work the other way:

In the jif the cat wore a hat of a cat

This obvious misspelling must be fixed, we shall correct this to:

In the gif (as in graphic) the cat wore a hat of a cat

Rules

You may assume all words that contain the letter g have the hard g sound (as in gravy) and all words that contain the letter j have the j sound (as in jam)
Words will never have both g and j (Will add more specific rules later)
Words must be picked at random each item with the same chance of being picked
Words may be supplied through an array or the closest alternative for your language.
Case must be preserved E.g. GiF -> JiF.
You may write a program or a function

Examples

Input and output separated by a single line:

graphic, jar, jam, gram
I saw a jif of how to pronounce gif that showed gif is pronounced jif

I saw a gif (as in graphic) of how to pronounce jif (as in jar) that showed jif (as in jam) is pronounced gif (as in gram)

gravy, jeff
G is for gif, h is for jif, i is for gif, j if for jif

G is for jif (as in jeff), h is for gif (as in gravy), i is for jif (as in jeff), j is for gif (as in gravy)

Is the assumption that, if there's more gif/jifs than input words, that you cycle through the g and j words independently (i.e. for gravy, jar, jam, gram, you cycle through gravy, gram for jif and jar, jam for gif)? And do we have do anything special for soft g words, e.g. generate? — Sp3000, Oct 23 '15 at 12:28
@Sp3000 forgot to specify that. I've made it so all words containing "g" are the hard g sound — Downgoat, Oct 23 '15 at 22:49
Has this challenge been posted? If not, may I take control of it? — Neil A., Jun 5 '17 at 23:09
@NeilA. You may but I don't think it'll be well received because it's a simple find/replace — Downgoat, Jun 6 '17 at 21:47
@Downgoat: I will make a new answer with the same core idea but a few changes. Feel free to delete this if you wish. — Neil A., Jun 6 '17 at 21:52

Mr Public · Accepted Answer · 2016-09-27 17:25:23Z

Largest Number Given Digits and Operators

Challenge

Given a list of digits (0-9) and operators (+, -, /, *), output the largest number that can be formed using those digits and operators, as well as the mathematical formula used to create this number.

Rules

All digits and operators must be used once and only once
Parenthesis may be used in the outputted mathematical formula
The outputted mathematical formula must be valid in an interactive Python shell (Note, this means ["--", "---", etc.], "//", "**", and ["++", "+++", etc.] are all valid operations that can be used in the output)
Base 10 will be used
For multiple different formulas that result in the same maximum number, output whichever one
Input may contain any number of digits and operators
Answers can be a function or program, and will be scored in bytes
No loopholes or built-ins

Example I/O

Input: [1, 4, 3, *, +]
Output: +31*4
        124

Input: [1, 2, 0, '+']
Output: +210
        210

This is rather similar to a number of existing questions, and may be closed as a duplicate. If you want to try to get it ready to post regardless, the use of the word "operators" in the first sentence is misleading given the later reference to combining those characters to form operators like **; and the question needs a complete list of permitted operators and what they do. People shouldn't have to find a Python language reference to know what // means, for instance. — Peter Taylor, Sep 28 '16 at 8:47
Related: Largest number printable, Can you surpass Γ<sub>0</sub>?, and What is the largest possible number that can be written in 10 seconds?. — Simply Beautiful Art, Jul 31 '17 at 23:22

Fatalize · Accepted Answer · 2016-09-28 12:01:35Z

0

Interleave your code with the input

Given an input string, interleave this string with the source code of your solution.

For example, if your code is abcd and the input is 1234, then your program must output 1a2b3c4d.

If your code is shorter than the input, then it must loop back to the beginning of your code. For example, if your code is abcd and the input is 123456, then your program must output 1a2b3c4d5a6b.

If your code is longer than the input, then only part of your code will be interleaved with the input. For example, if your code is abcd and the input is 12, then your program must output 1a2b.

Inputs and outputs

The input string will only contain characters which are valid string characters in your language.
The input may be taken through STDIN, as a function argument, or anything similar.
The output may be printed to STDOUT, returned from a function, or anything similar.

Scoring

This is code-golf, so the shortest answer in bytes wins.

answered Sep 28 '16 at 12:01

Fatalize

32.9k14 silver badges21 bronze badges

\$\begingroup\$ I'm not even sure that this is possible. \$\endgroup\$ – Fatalize Sep 28 '16 at 12:01
2

\$\begingroup\$ Why would it not be possible? The only potential problem I see is being closed as a dupe for being a straightforward generalised quine. \$\endgroup\$ – Peter Taylor Sep 28 '16 at 12:05
\$\begingroup\$ @PeterTaylor I don't understand how being a "straightforward generalised quine" makes it a dupe (of what?). I don't see how this is more straightforward than say this challenge nor do I think it is a dupe simply because source code is involved. \$\endgroup\$ – Fatalize Sep 28 '16 at 12:09
2

\$\begingroup\$ meta.codegolf.stackexchange.com/a/8595/194 \$\endgroup\$ – Peter Taylor Sep 28 '16 at 13:28

add a comment |

Balázs Sáros · Accepted Answer · 2016-09-29 18:35:54Z

The one-looper ASCII box

Intro

I saw this one in one of my university programming textbooks as an "advanced" exercise and I thought it would fit very well here.

Task

Your program have to ask for an input number and draw a box with the size of the given number and a cross in it.
Example if the number is 7:

+-------+
|\     /|
| \   / |
|  \ /  |
|   X   |
|  / \  |
| /   \ |
|/     \|
+-------+

Example if the number is 10:

+----------+
|\        /|
| \      / |
|  \    /  |
|   \  /   |
|    \/    |
|    /\    |
|   /  \   |
|  /    \  |
| /      \ |
|/        \|
+----------+

The minimum width is 1 and it looks like this:

+-+
|X|
+-+

Notice that with an odd size, there is an X in the middle.

The hard part

In your program only one function is allowed (main) and in the main function there can be only one loop and that loop can only have one statement which can't be if. The shortest answer wins!

note: Sorry for the messy description but I had to translate it from my native language.

Language specific challenges are discouraged, as per meta.codegolf.stackexchange.com/a/8058/48538. Good luck. — user48538, Sep 29 '16 at 18:27
do X without Y is confusing, especially when some internal things in languages use loops to achieve certain functionallity — downrep_nation, Sep 29 '16 at 20:42

downrep_nation · Accepted Answer · 2016-09-29 20:53:02Z

Interpret loose ranges code-golf

ListSharp is an interpreted programming language that has many features, one of those features is a 1 index based range creator that works like this:

You define a range as (INT) TO (INT) or just (INT) where both or the single int can go from min to max int32 value

Then you can use those ranges to extract elements of an array without fearing to overstep it's boundaries

therefore:

1 TO 5 generates: {1,2,3,4,5}

3 generates: {3}

Ranges can be added up using the AND operator

1 TO 5 AND 3 TO 6 generates: {1,2,3,4,5,3,4,5,6}

remember this works with negative numbers as well

3 TO -3 generates: {3,2,1,0,-1,-2,-3}

The challenge is the following:

Input

A character array and the previously defined range clause as a string

Output

The elements at the 1 index based locations of the range (non existing/negative indexes translate to an empty character)

How to win

Create the program with the shortest byte count

Test cases:

input array is:
{'H','e','l','l','o',' ','W','o','r','l','d'}

range clause:
"1 TO 3" => {'H','e','l'}
"5" => {'o'}
"-10 TO 10" => {'','','','','','','','','','','','H','e','l','l','o',' ','W','o','r','l'}
"0 AND 2 AND 4" => {'','e','l'}
"8 TO 3" => {'o','W','','o','l','l'}
"-300 AND 300" => {'',''}

correct, i forgot that! its code-golf and i dont know how to add the tag — downrep_nation, Sep 29 '16 at 20:50

Neil · Accepted Answer · 2016-09-30 07:51:28Z

Balanced Columns

I have a number of paragraphs of various heights which I would like to be distributed between some columns as evenly as possible. Here evenly means that you should minimise the total height of the tallest column, and then maximise the height of the shortest column, excluding empty columns.

The input will be an integer, representing the number of columns to be output, and an array of integers, representing the paragraph heights in lines. There is more than one way to represent the output; it could be an array (one for each column) of arrays of paragraphs, or it could be an array (one for each paragraph) of columns. (Please indicate whether your arrays are 0- or 1-based.) You may use any convenient format for (e.g. the number of columns as a command-line parameter and the array on STDIN) for I/O.

Because the paragraphs are double-spaced, there will be at least two lines in each paragraph, but if you prefer, your answer can take the double-spacing into account internally.

Within each column, paragraphs should be listed in ascending order, and the columns should be listed in ascending order of their first paragraph. Examples:

2, [2, 3, 4, 5, 6] -> [2, 3, 5], [4, 6] or [0, 0, 1, 0, 1]
3, [2, 3, 4, 5, 6] -> [2, 5], [3, 4], [6] or [0, 1, 1, 0, 2]
4, [2, 3, 4, 5, 6] -> [2, 3], [4], [5], [6] or [0, 0, 1, 2, 3]
5, [2, 3, 4, 5, 6] -> [2, 3], [4], [5], [6] or [0, 0, 1, 2, 3]

Note that in the last example the height could not be reduced by adding the extra column so in this case only four columns could be utilised.

If it's not a requirement to use every column (as indicated by your last example), that should be called out explicitly rather than inferred. — AdmBorkBork, Sep 30 '16 at 14:02
@TimmyD "maximise the height of the shortest column, excluding empty columns" not explicit enough for you? — Neil, Sep 30 '16 at 17:25
Yeah, as I didn't understand that to mean that I could optionally choose to have empty columns if it made the output more even. Maybe "explicit" wasn't the right word in my comment, but it could be more clear. — AdmBorkBork, Sep 30 '16 at 17:57

Community · Accepted Answer · 2017-04-13 12:39:23Z

0

No, this challenge is not this

Where is my error?

My compiler has broken down and now it is only showing the index of the character which the error is on.

In this challenge you will write a program to point to the given character.

Examples

Input:

if (goat == Downgoat) {
    print(Downgoat));
}

Output:

1 | if (goat == Downgoat) {
2 |     print(Downgoat));
  |                    ^
3 | }

Spec

TODO

edited Apr 13 '17 at 12:39

Community♦

1

answered Sep 30 '16 at 22:06

Downgoat

27.1k2 gold badges28 silver badges39 bronze badges

\$\begingroup\$ I was going to suggest giving an {x, y} pair as input, but that would make the challenge substantially easier. \$\endgroup\$ – ETHproductions Sep 30 '16 at 22:40
\$\begingroup\$ What if there are more than ten lines? \$\endgroup\$ – Conor O'Brien Oct 5 '16 at 1:14

add a comment |

noɥʇʎԀʎzɐɹƆ · Accepted Answer · 2016-10-10 02:12:08Z

First 100 prime numbers in Wentelx87 code-golf

Wentel consists of, at the basic level, a memory pointer and an instruction pointer. Instructions are stored loaded into memory. The execution pointer moves to the right after executing the instruction at that memory pointer.

The program is loaded into rightmost slot of memory. For example, if your program is 0010 0000 0101 0100, then the virtual machine will look like this when started:

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000 0101 0100 (memory)
                                                            ^                   (execution pointer)
^                                                                               (memory pointer)

(from README)

Wentel documentation examples, thorough and clear explanation here.

Wentel is language that is very hard to program in. Unlike brain**k, functions and GOTOs can be implemented. It emulates real machine code/assembly much better than brainf**k.

Wentel is a simple language.

instructions are held in the rightmost cells, one cell = one instruction
execution pointer starts out on first instruction
execution pointer moves right
the same cells that hold memory hold instructions.
these are the opcodes:

0000 - no-op

0001 - if the current address's value is equal to the value stored by the adress defined by the next word, move the execution pointer to the address pointed to the next word after the word after the current address.

0010 - move memory pointer to address specified by next word.

0011 - deposit the current address of the execution pointer into the current memory address

0100 - increment current memory address

0101 - decrement current memory address

0110 - move memory pointer left

0111 - move memory pointer right

and here are the specialized opcodes for output.

1000 - output 0

1001 - output 1

That was a boiling down of Wentel. Please read the full docs. Now for the actual challenge. Output the first 100 prime numbers, separated by spaces, in Wentel.

This is code-golf, so the shortest answer in bits wins.

If you want to encourage an answer to an existing question in a new language, the way to do it is with a bounty on the existing question. If you're worried about losing your rep because no answers will be posted, see meta.codegolf.stackexchange.com/q/5243/194 — Peter Taylor, Oct 10 '16 at 8:33

Geno Racklin Asher · Accepted Answer · 2016-10-12 17:57:34Z

0

Is this Rubik's Cube Solvable?

The challenge: find out if a rubik's cube configuration is solvable.

Takes input as a multidimensional array. An example for a solved cube would be

[
 [
  [0,0,0],
  [0,0,0],
  [0,0,0]
 ],
 [
  [1,1,1],
  [1,1,1],
  [1,1,1]
 ],
 [
  [2,2,2],
  [2,2,2],
  [2,2,2]
 ],
 [
  [3,3,3],
  [3,3,3],
  [3,3,3]
 ],
 [
  [4,4,4],
  [4,4,4],
  [4,4,4]
 ],
 [
  [5,5,5],
  [5,5,5],
  [5,5,5]
 ]
]

starting on the sides, going round, then top, then bottom. This input would give an output of 1, since it is solvable (very, very solvable). A (small) net of this solved cube would therefore be:

     _
 _ _|4|_
|0|1|2|3|
 ¯ ¯|5|¯
     ¯

The result of the program should be a truthy/falsey value, printed to STDOUT or similar. This is code-golf, so shortest answer in BYTES wins. Standard loopholes apply.

code-golf

edited Oct 12 '16 at 17:57

answered Oct 12 '16 at 17:14

Geno Racklin Asher

4662 silver badges2 bronze badges

\$\begingroup\$ What is the winning criterion? \$\endgroup\$ – acrolith Oct 12 '16 at 17:16
\$\begingroup\$ shortest code. I'll add code-golf as a tag now. \$\endgroup\$ – Geno Racklin Asher Oct 12 '16 at 17:20
\$\begingroup\$ I think you've got an extra 2 side in your example. \$\endgroup\$ – AdmBorkBork Oct 12 '16 at 17:55
\$\begingroup\$ whoops. Thanks for pointing that out. I will add some test cases soon. \$\endgroup\$ – Geno Racklin Asher Oct 12 '16 at 17:57
\$\begingroup\$ Add for people less familiar with the cube group that it has 12 = 2 * 2 * 3 orbits, 2 because you can't only exchange edges, 2 because you can't only flip an edge and 3 because you can't only turn a corner \$\endgroup\$ – Ton Hospel Oct 12 '16 at 22:25
\$\begingroup\$ codegolf.stackexchange.com/q/10768/194 . There's no fundamental difference between solving it and testing whether it can be solved. \$\endgroup\$ – Peter Taylor Oct 13 '16 at 7:21
\$\begingroup\$ @PeterTaylor I'd say there is a big difference. Trying to solve a cube is pointless if it's impossible to begin with. This is about spotting which cubes have been tampered with. \$\endgroup\$ – Geno Racklin Asher Oct 13 '16 at 9:27
\$\begingroup\$ Do you have a reference implementation which uses an approach other than trying to solve it and seeing whether you get stuck? (Also, if it is possible to do it without solving, I strongly recommend trying to find a way to prohibit brute-force solving, because that can be very short). \$\endgroup\$ – Peter Taylor Oct 13 '16 at 10:01
\$\begingroup\$ Not yet, but I'm working on it \$\endgroup\$ – Geno Racklin Asher Oct 13 '16 at 12:52

add a comment |

jacksonecac · Accepted Answer · 2016-10-14 15:33:15Z

Image Smoothing

Input into your program a black and white image. (png, jpg, etc)

Convert the image to a 2-d matrix of pixels. Where each index is the grayscale value of the image.

Take each index of the matrix and average the 8 pixels around it. Then replace that index with the average.

For example if you had:

120 80  60
20  10  30
40  100 05

If you were finding the average for 10, the result would be 56.875. Round to up to the nearest integer (57) and replace the index. The result of this iteration would be

120 80  60
20  57  30
40  100 05

If you are finding the average for a pixel on an edge then only take values that are valid. In the example above if you were finding the average for '20' You would only consider 112, 80, 57, 100, and 40, which is 79.4 rounded to 80.

You may start at any index of the graph but it must be in order, for example of you must go right - left, left - right, up - down, or down - up. You may not go something like randomly pick the indices to average.

Once the averaging is complete, convert the matrix back into a new image.

display the new image as the output of the program. (Or save it and add it in your solution). The result of this process should be a normal crisp looking image and the result would be a smoothed out image.

Please provide your code and start and end image (SFW please) and remember this is code-golf so the shortest code wins!

Good Luck and have fun!

cat · Accepted Answer · 2016-10-15 09:32:06Z

code-golf internet

Implement BozoCrack

Designed to show why MD5 is a bad solution to password hashing, BozoCrack, for the uninitiated, is a rather simple and efficient method of cracking MD5 hashes. It doesn't brute force, use rainbow tables or indeed, any sort of math at all.

Instead, it finds the key by searching google for the hash and comparing the hash of each word in the results with the input.

Your task is simple: given at least one valid MD5 hash in a reasonable input format, find their source texts using Google and return or print to stdout the results.

In fact, you could probably arrive at the answer by finding the word in the page with the most occurrences -- you needn't use the results for a dictionary attack, but you must use Google.

The inputs can be given as an array of strings, as program arguments, space or otherwise delimited strings on standard input or in a file, etc -- whatever's easier for you, but make sure you specify in your answer how the input is taken.

Example inputs / outputs:

Input                            : Output
fcf1eed8596699624167416a1e7e122e : octopus
bed128365216c019988915ed3add75fb : passw0rd
d0763edaa9d9bd2a9516280e9044d885 : monkey
dfd8c10c1b9b58c8bf102225ae3be9eb : 12081977
ede6b50e7b5826fe48fc1f0fe772c48f : 1q2w3e4r5t6y

Of course, you may use your language's library function for computing the md5sum of a string -- but please, don't use any functions or libraries designed to solve exactly this task, e.g. Python's PyBozoCrack and the original BozoCrack.rb are disallowed.

In the unlikely event there are no results for a sum, print "NO RESULTS" to stdout instead.

Nitpicking: 1. There's nothing special about MD5 here. Using any hash function without a salt has the same problem. 2. It sorta does use rainbow tables, just not locally stored ones. — Dennis, Oct 18 '16 at 16:46
@Dennis The github description says Instead of rainbow tables, dictionaries, or brute force,.., which is even more incorrect, so I made it a little less wrong :) It does work for any hash algo but it works best for MD5 — cat, Oct 18 '16 at 17:02

Sunny Pun · Accepted Answer · 2016-10-18 17:25:07Z

AlphaGo..olf?

code-golf

(Slight paraphrased) Extract from Wikipedia:

AlphaGo is a computer program developed by Google DeepMind in London to play the board game Go and is the first computer Go program has beaten a 9-dan professional without handicaps.

In order to appreciate the Go art more, let's try to simulate what happens to the game when a move is made!

Input

The input will be:

a 4x4 board, (Here . denotes empty, o and x denotes different color of stones held by the 2 players respectively for illustration. Any standard input formats (2d array, array as sequence of alternative moves...) are welcomed as we like nice algorithms!)
a move to be made (Like A4, B2. You may also like to use 0-indexed and both numeric indices like (0,0)..(3,3)) For simplicity's sake, the move to be made is always with o (i.e. always the same color).

Output

The board after the move is made. Stones of the opposite color (i.e. x) will be taken away iff there are no more connected x that has at least 1 . in its 4-neighbor (Up, Down, Left, Right).

Examples

  Input | Move | Output
  ABCD  |      |
1 ....  | A1   | o...   (case 1: all stones remains on board)
2 ....  |      | ....
3 ..x.  |      | ..x.
4 ....  |      | ....
--------+------+--------
  ....  | B1   | .o..
  oxo.  |      | o.o.   (case 2: x taken away: the only . is taken)
  .ox.  |      | .ox.
  ....  |      | ....
--------+------+--------
  ..o.  | B1   | .oo.
  oxxo  |      | o..o   (case 3: >1 x taken away: the only . is taken)
  .oxo  |      | .o.o
  .xo.  |      | .xo.
--------+------+--------
  o.xo  | B1   | oo.o
  ..o.  |      | ..o.   (case 4: Edge case)
  ....  |      | ....
  ..o.  |      | ..o.
--------+------+--------
  x.o.  | B1   | .oo.
  ooxo  |      | ooxo   (case 5: Corner case)
  ...o  |      | ...o
  ..o.  |      | ..o.
--------+------+--------
  xxxx  | B2   | ....
  x.xx  |      | .o..   (case 6: Enclosed by Board case)
  xxxx  |      | ....
  xxxx  |      | ....
--------+------+--------
  .oxx  | C2   | .o..
  ox.x  |      | o.o.   (case 7: Enclosed by o case)
  oxxx  |      | o...
  .ooo  |      | .ooo
--------+------+--------
  .xo.  | A1   | o.o.
  xo..  |      | .o..   (case 8: taking multiple groups case)
  o...  |      | o...
  ....  |      | ....
--------+------+--------

Rules

This is code-golf thus the shortest code wins.
Please kindly provide explanations and ways to test the solutions!
The Input board can be assumed to be correct: there will be neither x that without a connected x with ., nor a group of o surrounded by x without .
The Input move can be assumed to be legitimate: either it won't be a position surrounded by x, or it must take away some x to free . for the o to live. (ref. case 6, 7, 8)
The output must be the board, it may or may not be in the same format as the input (if you take input as 2 arrays of o and x positions, say). Output that only shows the stones that are taken away after the move is made will not be accepted.
Again, feel free to play with the standard input formats. Hope to see interesting 1 and 0 playing Go instead of o and x :P

Meta Questions

I don't know if this may be too hard. Would it be better if I allow golfers to fail some test cases and get penalty instead?
Should I stick with a 4x4 board or I can award minus scores if the solution can work with a 19x19 board?
If it is a yes to any of the above questions, which should be the number for the penalty / award?

Thanks!

If it can work with a 4x4 board it's probably scalable. I don't see any reason to have both; 4x4 seems less daunting, but 19x19 would be more satisfying to program for, even if it is pretty much the same thing. — wizzwizz4, Oct 18 '16 at 17:42
The explanation of what exactly the program should do is rather poor. I think I can work it out, but only because I've played Go in the past. IMO the question would be greatly improved by removing the current introduction and replacing it with an explanation of liberties (which in essence is half of the rules of Go, isn't it? That plus ko). As far as size, don't do bonuses; just require answers to handle a board of any rectangular size, with a guarantee that each line is the same length. Or maybe make each dimension at least two. Then add test cases to cover the minima. — Peter Taylor, Oct 19 '16 at 11:52

Mego · Accepted Answer · 2016-10-20 01:12:00Z

Categorize the asymptotic behavior of a consumer/producer system

Given two functions P(t) and C(t), output the correct category for the behavior of P(t)-C(t) as t goes to positive infinity:

Ideal: P(t)-C(t) goes to 0.
Stable: P(t)-C(t) oscillates, with the time spent as a positive value equal to the time spent as a negative value within a single oscillation period.
Hungry: P(t)-C(t) either converges to a negative value, or oscillates, with more negative values than positive values in one oscillation period.
Starved: P(t)-C(t) diverges, approaching negative infinity.
Saturated: P(t)-C(t) either converges to a positive value, or oscillates, with more positive values than negative values in one oscillation period.
Oversaturated: P(t)-C(t) diverges, approaching positive infinity.

Rules

The expected output will always be one of the above cases - you don't have to worry about other cases
P(t) and C(t) will always be real-valued continuous functions that only consist of the following operations: addition, subtraction, multiplication, division, exponentiation (for constants a and b and parameter t, a^b, t^a, and a^t are all allowed), principal roots (real roots, only when they exist, and only the positive root when there are 2 real roots), logarithms, and basic trigonometric functions (sine and cosine of arbitrary values, and tangent for values that are not odd multiples of pi/2)
Input may be in any reasonably format (string, function object/pointer, mathematical function object, etc.)
You may use any unambiguous set of 6 values for output (like [1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4, 5], [Ideal, Stable, Hungry, Starved, Saturated, Oversaturated], or [0, ~, -, -∞, +, +∞])

Test Cases

TBD

Sandbox Notes

Are the definitions and rules clear?
Are there any I/O methods that should be explicitly allowed or forbidden that aren't covered by the current rules?

I suspect that this is extraordinarily difficult and possibly formally undecidable. See Richardson's Theorem. — xnor, Oct 20 '16 at 4:22
@xnor Richardson's Theorem only applies to finding zeroes of functions and deciding if two functions are equal everywhere. It doesn't have anything to do with asymptotic behavior. As for the challenge being extraordinarily difficult - it's not meant to be an easy challenge. — Mego, Oct 20 '16 at 4:55
Actually, I can prove it's undecidable. Let A be an elementary function for which you want to decide whether it is everywhere 0, in contradiction of Richardson's theorem. Then, A(e^t * sin(t)) goes to 0 as t->∞ if and only A is identically 0. This is because any x for which A(x) is nonzero would correspond to an infinite number of t with x=e^t*sin(t), causing the limit to be nonzero. So, by running an algorithm for your problem and checking whether it outputs (1) or not, we'd be able to solve an undecidable problem. — xnor, Oct 20 '16 at 5:18
@xnor Good catch, I didn't consider that. Would it be possible to limit the types of functions such that it would be deciable, and all of the cases would be possible? — Mego, Oct 20 '16 at 5:44
I don't think so. Without sin or cos, you can't get oscillation, but that's basically enough for the undecidability to apply. — xnor, Oct 20 '16 at 5:46
@xnor Shame. I think I'll rewrite this using discrete functions, in a manner so it is decidable. — Mego, Oct 20 '16 at 5:48

jimmy23013 · Accepted Answer · 2016-10-21 07:23:47Z

0

(Need a title.)

Your task is to write 3 programs (or functions) that check if the input is a string of balanced brackets satisfying all the following criteria:

The number of []s is always less than or equal to the number of ()s surrounding each position.
The number of {}s is always less than or equal to the sum of the numbers of ()s and []s surrounding each position.
The number of <>s is always less than or equal to the product of the number of () [] and {}s surrounding each position.

You can assume that:

There are only the characters ()[] in the input of your program 1.
There are only the characters ()[]{} in the input of your program 2.
There are only the characters ()[]{}<> in the input of your program 3.

Your score is the product of (the length of each program + 1). Lowest score wins.

Examples

(To do.)

edited Oct 21 '16 at 7:23

answered Oct 19 '16 at 12:58

jimmy23013

34k23 silver badges33 bronze badges

1

\$\begingroup\$ I don't understand the first tie-breaker. What is a "program number"? \$\endgroup\$ – Peter Taylor Oct 19 '16 at 14:13
\$\begingroup\$ @PeterTaylor: You can choose to make up to 3 programs. Program 1 handles 2 bracket-types, Program 2 handles 3 bracket-types and Program 3 handles 4 bracket-types. If person A has made programs 1 and 2 and person B has made programs 2 and 3. Person B wins the tie-breaker as his program numbers (3,2) are higher (and thus more advanced). \$\endgroup\$ – Emigna Oct 20 '16 at 9:46
\$\begingroup\$ If Emigna is correct that this is a task where you can choose to not do the hardest two thirds of it, then that's stupid. I had assumed that the "up to three programs" was to allow people to write a single program to maximise code reuse between the three subtasks, not to allow skipping the subtasks entirely. \$\endgroup\$ – Peter Taylor Oct 20 '16 at 10:21
\$\begingroup\$ In any case, the first 2 tie-breakers is unlikely to see use as I'm sure someone will do all 3 and then only the program lengths will determine the score. \$\endgroup\$ – Emigna Oct 20 '16 at 10:47
\$\begingroup\$ Yes, removed that part. \$\endgroup\$ – jimmy23013 Oct 21 '16 at 7:24

add a comment |

miles · Accepted Answer · 2016-10-22 18:54:54Z

Fastest Cashier in the West

You're trying to design an automatic cashier that is able to dispense the correct amount of change in any denominations as quickly as possible. Your goal is to implement a program that accepts a target integer T ≥ 0 which is the amount you're trying to make change for, and a set of positive integers {c₁, c₂, ..., c_n} which are the values of each coin where you have an infinite number of each, and output all possible solutions for making change with those types of coins.

For example, if you're trying to make change for 123 and the coins available are {12, 16, 20, 27}, then there are 8 possible solutions

12 16 20 27  (123)
 0  1  4  1  means zero 12's, one 16, four 20's, one 27
             also 0*12 + 1*16 + 4*20 + 1*27 = 123
 0  6  0  1
 1  4  1  1
 2  2  2  1
 3  0  3  1
 4  3  0  1
 5  1  1  1
 8  0  0  1

Format

The input will be formatted as

T
N
c1
c2
...
cN

where T is the target value, N is the number of coins, and each cK is the value of coin k. Also, the coins will be listed in ascending order.

For example,

The output will be format as

x11 x12 ... x1N
x21 x22 ... x2N
...
xM1 xM2 ... xMN

where M is the number of solutions and N is the number of coins. Each line will contain the number of each coin needed to reach the target value separated by spaces. You may have trailing whitespace on each line.

For example, the output to the input above would be

You may output the solutions on each line in any order, but each solution must be unique.

Rules

This is fastest-code so your only goal is to make your program as fast as possible.
Builtins or libraries that solve this problem directly are not allowed.
In the interests of having fine submissions, the deadline will be by December 12, 2016, which is almost two months.
Your program must be single-threaded. However, you are allowed to use SIMD instructions and any other features of the CPU.
The code will be ran on my machine which uses Fedora 24 x64 and has an i7-920 with 18 GB of memory.
Please provide compilation instructions and version information if your program requires it.
Please do not obfuscate your code unnecessarily. If I am suspicious of certain code and/or libraries, I reserve the right to ignore your submission.
This is optional but if you are using advanced mathematical strategies, commenting and explaining your program would be very much appreciated.

Thoughts

The test cases will be created and provided as a download if there is interest.

For scoring, there will be a hidden dataset that is ran when the deadline is reached for final scoring purposes. After this is complete, the hidden dataset will be released along with the winner.

For extra incentive, should I increase the best answer reward by including a bounty. Or maybe for the three fastest?

Is it okay to ban commercial products as I may not have access to some of them. It wouldn't be fair to allow Mathematica and not Matlab/Maple/etc.

@PeterTaylor: I have an implementation in Python that uses a memoized recursive function and I would say its performance is decent at best. I do agree that I/O could be a bottleneck but I could choose test cases that have few or no solutions. Using methods to calculate the Frobenius number would help find those, but I would still like to see a few cases with a large number of solutions. I see two options. First, I could require the output to be ordered so that results could be piped into another program and avoid hitting the disk while being verified. The second is to test each program twice, first with the output enabled to check the accuracy, and if accurate, the second run would be with the output disabled to measure the execution time.

Have you written and profiled a reference implementation? I would guess that for many inputs the bottleneck is going to be I/O rather than calculation, and that should be taken into account when timing. — Peter Taylor, Oct 22 '16 at 18:34
@PeterTaylor My response was a bit long so I added it to the question. — miles, Oct 22 '16 at 18:55
Please state the upper bounds for number of coins, cost, coin value, number of solutions... — feersum, Oct 23 '16 at 5:45

SEJPM · Accepted Answer · 2016-10-22 21:11:21Z

It's time to parse (everything)!

code-golf parsing

Introduction

The real world is hard. Internet standards suck. However they're used everywhere anyways. One standard in particular has been the source of a lot of trouble and frustration.
ASN.1
Abstract Syntax Notation 1
is used in many many places (including when parsing website certificates) and now it's up to you to implement a simple ASN.1 parser in your favourite programming language!

Specification

Input

Your input will be an ASN.1 encoded object. The encoding that is used will be PEM (thus it's all ASCII). You may take this input as a file, as STDIN, as a function argument as a string, as a byte sequence, whatever you like. The way your program takes the input should be documented however.

If you take file input, you may have the file name as an additional argument.
If you produce file output, you may have the file name as an additional argument.

Output

The output will be formatted ASCII text, this may be STDOUT, a returned string, a file, whatever, but document it.

What to do

You need to parse an ASN.1 object and return a nice textual representation of the content structure.
This means that there should be some sort of intendention whenever a nested structure is opened (by putting spaces or other signs in front of the identifier).
It also means that you should print the keyword whenever one is hit (also see the example).
You may but do not have to also output actual (decoded) contents or looked-up identifiers.

Warning

While I've always talked about an ASN.1 object, I actually had X.509 certificates in mind. So the parser should understand everything that occurs inside an

List of mandatory keywords:

SEQUENCE
OBJECT
UTCTIME
PRINTABLESTRING
SET
UTCTIME
NULL
OCTET STRING
BOOLEAN
UTF8STRING
BIT STRING
OBJECT IDENTIFIER
IA5STRING

Who wins?

This is code-golf, so the shortest answer in bytes wins!
Standard rules apply of course, built-ins are allowed.

Example Input and Output

Input: The Amazon.com X.509 certificate:

Example output:

SEQUENCE
   SEQUENCE
      [0]
         INTEGER
      INTEGER
      SEQUENCE
         OBJECT IDENTIFIER
         NULL
      SEQUENCE
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               PRINTABLESTRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               PRINTABLESTRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               PRINTABLESTRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               PRINTABLESTRING
      SEQUENCE
         UTCTIME
         UTCTIME
      SEQUENCE
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               PRINTABLESTRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               UTF8STRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               UTF8STRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               UTF8STRING
         SET
            SEQUENCE
               OBJECT IDENTIFIER
               UTF8STRING
      SEQUENCE
         SEQUENCE
            OBJECT IDENTIFIER
            NULL
         BIT STRING
            SEQUENCE
               INTEGER
               INTEGER
      [3]
         SEQUENCE
            SEQUENCE
               OBJECT IDENTIFIER
               OCTET STRING
                  SEQUENCE
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
                     [2]
            SEQUENCE
               OBJECT IDENTIFIER
               OCTET STRING
                  SEQUENCE
            SEQUENCE
               OBJECT IDENTIFIER
               BOOLEAN
               OCTET STRING
                  BIT STRING
            SEQUENCE
               OBJECT IDENTIFIER
               OCTET STRING
                  SEQUENCE
                     OBJECT IDENTIFIER
                     OBJECT IDENTIFIER
            SEQUENCE
               OBJECT IDENTIFIER
               OCTET STRING
                  SEQUENCE
                     SEQUENCE
                        OBJECT IDENTIFIER
                        SEQUENCE
                           SEQUENCE
                              OBJECT IDENTIFIER
                              IA5String
                           SEQUENCE
                              OBJECT IDENTIFIER
                              SEQUENCE
                                 UTF8String
            SEQUENCE
               OBJECT IDENTIFIER
               OCTET STRING
                  SEQUENCE
                     [0]
             SEQUENCE
                OBJECT IDENTIFIER
                OCTET STRING
                   SEQUENCE
                      SEQUENCE
                         [0]
                            [0]
                               [6]
             SEQUENCE
                OBJECT IDENTIFIER
                OCTET STRING
                   SEQUENCE
                      SEQUENCE
                         OBJECT IDENTIFIER
                         [6]
                      SEQUENCE
                         OBJECT IDENTIFIER
                         [6]
SEQUENCE
   OBJECT IDENTIFIER
   NULL
BIT STRING

Helpful ressources

Reference parser
TODO: Add more useful links and actual ASN.1 parsing description

@corvus_192 if your language has a built-in ASN.1 parser (!) I don't have any problems with built-ins and traditionally I always allowed them. — SEJPM, Oct 20 '16 at 19:26

Nathan Merrill · Accepted Answer · 2016-11-03 16:50:33Z

Simple Substitution Cipher Programming

A simple substitution cipher maps each unique character to another character. If my substitution cipher is [H->6, e->U, l->V, o->)], then Hello becomes 6UVV).

You must write a program A which inputs a string of text, and outputs the text after passing it through a substitution cipher.

You must also be able to handle your program, A, as input, printing out B. If possible, B then applies a different cipher, and prints out C, and so on, until you cannot repeat the process anymore, or until a duplicate program as been generated.

Your ciphers must:

Contain at least 2 substitutions, and every character in your program.
Change every character (i.e., no A->A)
Be unique on every substitution (i.e., if program A uses x->y, then program B must convert x into something other than y)
All be written in the same language (same version)

Your score is ByteCount(A)/NumIterations. You can assume that your input only consists of substitute-able characters.

For example, if A was Programming, and it generated p80G8AMM1NG, which generated u79)7%vvQ-), which finally generated Programming, then there were 3 ciphers applied, and a byte count of 11, so my score would be 11/3, or approximately 3.666667. If the final output was an invalid program, my score would still be the same.

That's literally my title. Regardless, after the cipher, the goal is to produce another program that also does a cipher — Nathan Merrill, Nov 2 '16 at 23:47
"If possible" seems to imply that B doesn't need to be a valid program, so I think this spec allows any program A which outputs a string of the same length as itself with a consistent mapping between the characters - i.e. it doesn't need to apply that mapping to its input. On my pedantic reading of the spec, X would be a valid CJam answer, scoring 1/1. In fact, on a pedantic reading of the spec the empty string would be a valid answer in various languages, looping immediately but scoring 0/1 and hence unbeatable. — Peter Taylor, Nov 3 '16 at 14:32
True, I should enforce a language length of 1. I'm ok with X being a valid submission, as I think there may be another CJam submission that can get a lower score. On the other hand, I'd be for requiring a minimum of 2 distinct characters, if that would make it more interesting — Nathan Merrill, Nov 3 '16 at 14:35

celtschk · Accepted Answer · 2016-11-04 01:47:30Z

Peano's quine

Your task is to write two programs in the same programming language.

The first program is simply a quine, in the following called "zero quine".

The second program, called succesdor program, is a program that gets a program text as input, and outputs another program text, according to the following rules:

The input text is either the zero quine, or code that is (or could be) the output of another run of the successor program.
The output is again a quine in the same language.
The zero quine, generated quines and successor program fulfil Peano's axioms. In particular:
1. The successor function does never output the zero quine, no matter what the input is.
2. The successor function produces different output when acting on different valid input.

In other words, the zero quine and the successor function together allow to generate an unbounded number of quines, one for each natural number.

The score is the total number of bytes of the zero quine and the successor program together.

Note that while there are several challenges that have programs returning longer versions of itself when run, I didn't find any that has a program transforming a proper quine into another proper quine.

Tags: code-golf quine

This is extremely similar to quine loops. It just needs a quine which has a literal (int or string) it ignores and a program which respectively increments it / appends a character to it. — Peter Taylor, Nov 4 '16 at 8:26

clismique · Accepted Answer · 2016-11-09 06:59:03Z

0

Match the BF output code-golf regex brainfuck

Your task is, when given a BF program as input and 256 1's on the line after the BF program, match the amount of 1's equal to the value of the pointer when the program halts.

For a BF tutorial, see here.

Example programs:

+++
(255 1's)

(The above program should match 3 1's.)

++[>+++>+++<<-]>
(255 1's)

(The above program should match 6 1's.)

Specs:

The tape in question is 10 long, with wrapping.
There is wrapping for the individual values: if it goes over 256, it goes back to 0.
There is no , or . in the BF code.
You are guaranteed that the code will terminate.
You may use any flavour you want.
You may match 1's in any position, as long as you match the correct amount of 1's.

This is code-golf, so shortest code in bytes wins!

Meta stuff:

How hard would this be to pull off? Is it even possible?
Anything I could improve with explanations?

edited Nov 9 '16 at 6:59

answered Nov 8 '16 at 5:12

clismique

6,5705 silver badges10 bronze badges

1

\$\begingroup\$ 1. I think it should be "the value of the memory cell under the pointer" rather than "the value of the pointer". 2. This is clearly impossible using regular expressions, but it is possible using Perl 5's regexes, which are Turing-complete. However, at that point you're really just using Perl wrapped in regex notation, so it's arguably a dupe of codegolf.stackexchange.com/q/84/194 \$\endgroup\$ – Peter Taylor Nov 8 '16 at 7:30
\$\begingroup\$ @PeterTaylor Your second claim is false. With a wrap around BF becomes a finite state machine. Thus even it's halting problem is solvable by a push down automaton (regex). It may be extremely hard but this problem is most certainly solvable. \$\endgroup\$ – Post Rock Garf Hunter Nov 8 '16 at 17:04
1

\$\begingroup\$ @WheatWizard, although my initial reaction was to agree with you, on further reflection I'm not entirely convinced. The halting problem for a finite state machine is trivial: they always halt. Since a BF program can enter an infinite loop, it's therefore not an FSM. It's true that any given program has a finite number of states, but the state includes the program counter and so the ecosystem as a whole can have an unbounded number of states. Consider that in execution we can jump back along the program string an arbitrary distance: how can a pushdown automaton remember the contents of a loop? \$\endgroup\$ – Peter Taylor Nov 8 '16 at 20:48
\$\begingroup\$ @PeterTaylor iirc finite state machines can loop infinitely however any loop must be periodic. I don't know why you claim finite state machines cannot loop. Toroidal Brainfuck fits every definition of a FSM I can find at the moment. It has a finite number of states and a well defined mapping of each state to another. I also don't understand what you mean when you say "Program counter" if you are referring to the instruction pointer it is certainly finite. Could you clarify this? I don't mean to be argumentative, but I do disagree with you. If I am incorrect I am sorry for wasting your time. \$\endgroup\$ – Post Rock Garf Hunter Nov 8 '16 at 23:36
\$\begingroup\$ @PeterTaylor If it helps, the input program is guaranteed to halt. Would it be easier to decide if there are a limited number of "moves" (i.e. 30,000 moves, 1 move = any +-><)? \$\endgroup\$ – clismique Nov 9 '16 at 5:03
\$\begingroup\$ @WheatWizard, the point with FSMs and the halting problem is that each state transition occurs with one character of the input, each character of the input is processed only once, so therefore the execution time is bounded by the length of the input. On the main point, I'm not saying that you're wrong: just that I'm not convinced. Perhaps the thing to do is to edit the question to rule out "cheating" by calling out to a general-purpose programming language and then see whether anyone finds a solution. \$\endgroup\$ – Peter Taylor Nov 9 '16 at 7:36
\$\begingroup\$ Limiting the runtime would certainly make it doable, because then the values which the program counter (or instruction pointer, they're synonymous) can reach are bounded, and so the total number of states is bounded by the number of memory states times the number of moves. It's not a practical bound, but in theoretical terms it's certainly good enough. \$\endgroup\$ – Peter Taylor Nov 9 '16 at 7:37
\$\begingroup\$ @PeterTaylor So I'm getting the "this is impossibly hard" gist - but is it on the same level as "Tetris in GoL"? I want to make a challenge that's difficult, but not THAT difficult. \$\endgroup\$ – clismique Nov 9 '16 at 9:59
\$\begingroup\$ I just realized that vanilla regex (without lookarounds) is a finite state machine and not a push down automaton. I think PeterTaylor is correct in assessing this as impossible. \$\endgroup\$ – Post Rock Garf Hunter Nov 9 '16 at 14:15

add a comment |

RudolfJelin · Accepted Answer · 2016-11-10 14:29:55Z

Find the highest product in a grid

The following problem was inspired by Problem 8 at Project Euler.

Write a program that takes a 2-dimensional block of digits and a number on a newline ("n") as it's input. Output value of the product of the n adjacent (read "in a straight line") digits in the that have the greatest product. Error cases don't need to be covered (eg. the grid is not rectangular, n is missing, n is bigger then the width/height as the block, etc.). Diagonal numbers are also adjacent.

Examples:

1932       
4836       
8490  -->  288
3          

53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881  -->  5832
16427171479924442928230863465674813919123162824586
4

43289
90283
03248  -->  error (print whatever)
34290
22

397432008949201741720 --> 72
2

Note: possible inputs below are equivalent:

2830
0309
8011 
4

2 8 3 0
0 3 0 9
8 0 1 1 
4

{{2, 8, 3, 0},
{0, 3, 0, 9},
{8, 0, 1, 1}}
4

And so on, it's not strict.

It's code-golf, so the shortest answer in bytes wins!

code-golf

PPCG as a whole isn't a fan of strict input formats. In particular, function (which are allowed by default) should probably be able to take a matrix and a separate integer as arguments. — Dennis, Nov 10 '16 at 1:20
@Dennis Thanks for notifying me, I didn't see that issue since I'm new to this site. I edited my proposal a bit also. — RudolfJelin, Nov 10 '16 at 14:31

FliiFe · Accepted Answer · 2016-11-10 20:47:13Z

Absolutely correct !

I have been given some homework, in which my Math teacher wants me to figure out what expression is represented in the graphs she gave me. Because it is long and painful to do every single one of them by hand, I want to automate it a bit.

The challenge

Given a graph as an input, output the equation represented, in human-readable format. That is, something like that:

y=-|x-3|+5

More generaly, the expression will always be of the form

y=±|x+a|+b

Where you have to replace a and b by their value. The function has to be simplified to its maximum (i.e. can not contain +0, -0, or +|x|);

The input

The input is given in ASCII.

             \       |       /             
              \      |      /              
               \     |     /               
                \    |    /                
                 \   |   /                 
                  \  |  /                  
                   \ | /                   
                    \|/                    
---------------------V---------------------
                     |                     
                     |                     
                     |                     
                     |                     
                     |                     
                     |                     
                     |                     
                     |

This represents the equation y=|x|. The graph is not always centered, and can be of any width and height.

/, \ are straight lines. A and V are verteces. - and | are the axes, and + is their intersection (if not covered by an other character).

Unit

A unit is two characters. for example, -- is one unit on the horizontal axis.

|
|

Is one unit on the vertical axis.

Tests

A test suite is available here. A line of #s is used to separate input from output. Output goes first, for clarity.

Laikoni · Accepted Answer · 2016-11-13 09:26:03Z

0

How Big is the Hyperbolic Round Table of Camelot?

There is a hyperbolic rogue-like game called HyperRogue, based on the truncated order-7 triangular tiling. (Each vertex is surrounded by two hexagons and one heptagon.) There is a place in this game called Camelot, where the Round Table sits. In the middle of the table is the Holy Grail. The table starts with a radius of 28, but each Holy Grail you collect increases the radius by 2. So my question is: given the number of Holy Grails collected, what is the area of the Round Table?

Assumptions:

The Holy Grail starts on a heptagon.
The heptagon the Holy Grail is on is the circle of radius 0.
A circle with radius n+1 comprises the circle of radius n and all the cells touching the circle of radius n.

Test Cases:

0 Holy Grails = 31659398 Tiles
1 Holy Grail = 93888285 Tiles
2 Holy Grails = 278432568 Tiles

Winning Criterion:

Shortest code wins! code-golf

edited Nov 13 '16 at 9:26

Laikoni

23.6k12 silver badges14 bronze badges

answered Nov 11 '16 at 22:34

Oliver Daugherty-Long

1752 bronze badges

2

\$\begingroup\$ This challenge is very unclear as it is right now. The end of the first part sounds like you are asking for A = (28 + n*2)^2 + pi, but instead of an area a number of tiles is given. To make it clear what exactly you are asking, you should add some graphical representation of the tiling, the circles ect. \$\endgroup\$ – Laikoni Nov 12 '16 at 23:15
\$\begingroup\$ @Laikoni I don't know how to add pictures, or format anything, actually. I'm trying to ask for calculating the area of a hyperbolic circle. Here's the image I want to add illustrating the geometry: en.wikipedia.org/wiki/File:H2_tiling_237-6.png \$\endgroup\$ – Oliver Daugherty-Long Nov 13 '16 at 3:30
1

\$\begingroup\$ I added some formatting. If you edit your question (and are not on mobile) in the top bar some formatting buttons appear. At the right of this bar is a ?-icon which provides further formatting help. \$\endgroup\$ – Laikoni Nov 13 '16 at 9:27
\$\begingroup\$ @Laikoni Thanks! I am on mobile, unfortunately. \$\endgroup\$ – Oliver Daugherty-Long Nov 14 '16 at 0:13

add a comment |

jacksonecac · Accepted Answer · 2016-11-14 19:50:59Z

Pay Best Card in Euchre

Input:

Firstly
An array of three cards representing the cards played by each player formatted like

[JD][10H][9S]

Representing

Jack of Diamonds, 10 of Hearts, and Nine of Spades.

As you always sit across from your team-mate in Euchre, the second element represents your team mate's play. Here, the 10H.

Secondly
A Single Char, String, etc representing the trump suit formatted like

S, D, C, H

representing

Spades, Diamonds, Clubs, Hearts

Thirdly an array of four cards representing your hand formatted like

[KD][JC][QH][AS]

representing

King of Diamonds, Jack of Clubs, Queen of Hearts, Ace of Spades

Objective:

Given the three inputs, output the best possible card to add to the cards that have been played such that it meets the following criteria:

It takes the hand if it can, if not output the least valuable card
It takes the hand if it can, however it will not trump your team mate unless it is unavoidable
If it can take the hand, it does so by using the least valuable card. (If you have an ace and a queen that can win the hand, you play the queen).

Output format like [JD]

Formatting

A - Ace
K - King
Q - Queen
J - Jack
10 - Ten
9 - Nine

H - Hearts
D - Diamonds
S - Spades
C - Clubs

10H, 9D, JD, QH, AD, 9C, 10C

Examples

In: [QD][KD][9C], "C", [AH][JH][QH][9H]

Out: 9H

Reason: As clubs are trump, the 9C is winning the hand, we are unable to take the hand so we should discard our lowest card, here the 9H

In: [QD][KD][AD], "H", [AH][JH][QH][9H]

Out: 9H

Reason: As Hearts are trump, the Ace of Diamonds is currently winning the hand, we are able to trump the hand so we should use our lowest card, here the 9H

In: [QD][KD][10D], "H", [AD][JH][QH][9D]

Out: 9D

Reason: As diamonds are trump and we are currently winning the hand, we should play the 9D because our partner currently is winning the hand, so we want to play the 9D over the AD

In: [QH][KH][JH], "D", [AD][JD][QH][9D]

Out: QH

Reason: As Diamonds are trump our opponents are winning with the left Bower JH We have the right bower but cannot trump him because QH was led and we must follow suit, the QH

In: [QH][KH][JH], "D", [AD][JD][QC][9D]

Out: JD

Reason: As Diamonds are trump our opponents are winning with the left Bower JH We have the right bower and since we have no Diamonds we can trump over him with the JD

Euchre Card Strengths

If Hearts is trump:

JH
JD
AH
KH
QH
10H
9H

See the Euchre Rules if you are unfamiliar with the strength of different cards in Euchre

Since this is Code-Golf the shortest code wins!

Good Luck and have fun!

Community · Accepted Answer · 2017-04-13 12:39:27Z

Python Kolmogorov Complexity Golfer

Python is actually pretty good at some Kolmogorov Complexity challenges (compared to other non-golfing languages), from string multiplication being extremely short, to defining variables requiring no types.

Your challenge is to make a program that shortens Python code for Kolmogorov Complexity challenges. You can use anything, not just the usual functions that people typically use.

Your score is the sum of all the bytes for each of the ten test cases, and the winner is the submission with the lowest score.

Test Cases

I don't know about the rules for each challenge, but for this one, you may print extra spaces after each line and extra newlines at the end of the text.

Note

I don't know how to tag this.

Harald Korneliussen · Accepted Answer · 2016-11-16 14:56:28Z

Enumerate all the binary matrices

Your task is to write a pair of programs or functions. The first should take a single nonnegative integer, and return some matrix where all elements are 0 or 1 (or true/false). The second should take a matrix of the same form, and return a nonnegative integer.

The two programs should form a bijection, so that every possible matrix is mapped to exactly one nonnegative integer, and every integer to the corresponding matrix. The matrix with no elements must be included, but we consider all matrices with no elements as identical (i.e, there is no 0x3 matrix.)

To clarify, the dimensions of the matrix is not a separate input. You must work out a way to represent all possible dimensions. For instance, you could start off enumerating them like this:

0 <-> []
1 <-> [0]
2 <-> [1]
3 <-> [0;0]
4 <-> [0;1]
5 <-> [1;0]
6 <-> [1;1]
7 <-> [0,0]
8 <-> [0,1]
9 <-> [1,0]
10 <-> [1,1]

But you can also enumerate them in some different order, as long as all matrices of all dimensions can be reached eventually.

You may output and input the integer as a bigint if your language supports that, or as an unbounded string or array if it doesn't. It should however not be limited to a machine word size.

You may output the matrix in any format you choose, as long as the elements of the matrix, and the rows/columns of the matrix are clearly distinguishable.

Whatever output formats you choose, the other program must accept input in the same format. Your functions or programs may opt to print the result rather than return it.

Standard loopholes are forbidden. This is code golf, so the shortest answer wins.

code-golf number binary-matrix

1. It would be helpful for the title to be more explicit that the size of the matrix isn't an input: my initial reaction was that this was yet another "Count from 1 to 2^x" question, and I had to read it carefully to overcome that reaction. 2. Please clarify the situation with empty matrices. Should the matrices include 0 x 1, 2 x 0, etc. dimensions? And if so, how can that be represented unambiguously in input? — Peter Taylor, Nov 16 '16 at 14:34

PlatinTato · Accepted Answer · 2016-11-16 15:27:25Z

0

Challenge

You are the owner of a local supermarket, and your cashier doesn't seem to do the work you told him/her to do. He/She is never on time, returns too much change and doesn't really show optimism at the workplace. So you, as the space saving, but ruthless owner opt to replace him/her.

Rules

The programm should initially take 2 numbers as input, the first beeing the price, and the second the amount you are paying. If you are paying enough it should output the change in 100,50,20,10,5,2,1 notes, always maximizing the amount of high notes. If you aren't, you may output anything indicating a wrong input.

Examples

cashier 100 500
4 100
0  50
0  20
0  10
0   5
0   2
0   1

cashier 600 500
0

Scoring

This is code-golf, so the shortest byte amount wins :) Good luck!

answered Nov 16 '16 at 15:27

PlatinTato

891 bronze badge

\$\begingroup\$ Does the output format matter, or are we also allowed to have a different output format as long as we know how much 100 bills, 50 bills, etc. are used (like "4x100,0x50,0x20,0x10,0x5,0x2,0x1") ? Also, what if the price and amount paid is exactly the same? \$\endgroup\$ – Kevin Cruijssen Nov 16 '16 at 15:29
\$\begingroup\$ related (if not duplicated) \$\endgroup\$ – Rod Nov 16 '16 at 15:30
\$\begingroup\$ @KevinCruijssen the output format is fine. inputting the same amount paid as price results in "no chage" but the output shoudl still be 0x100... \$\endgroup\$ – PlatinTato Nov 16 '16 at 15:31
\$\begingroup\$ @Rod ah ok :/ didnt find anything in the direcition mine was going. i guess the title made it less findable :/ \$\endgroup\$ – PlatinTato Nov 16 '16 at 15:33

add a comment |

Oliver Ni · Accepted Answer · 2016-11-17 15:12:21Z

0

Fold the number!

Given a number n, fold the number as follows: (ex. 30)

First, convert it to binary.

Add one 0 to the start if it has an odd number of digits.

Now, take the second half of the number, reverse it, and put it under. For example, abcd would turn into ab dc (where is a newline):

011
011

Add one 0 to each line if it has an odd number of digits.

0011
0011

Now take the back of the whole thing and put it on the bottom, reversed:

Keep doing this until there is only one column, and read this from top to bottom.

00110011

Convert to decimal.

Remember, this is code-golf, so the code with the smallest number of bytes wins.

code-golf number base-conversion

edited Nov 17 '16 at 15:12

answered Nov 16 '16 at 6:31

Oliver Ni

9,5927 silver badges13 bronze badges

\$\begingroup\$ @Emigna Fixed.. \$\endgroup\$ – Oliver Ni Nov 16 '16 at 15:01
\$\begingroup\$ codegolf.stackexchange.com/questions/95458/folding-numbers \$\endgroup\$ – Magic Octopus Urn Nov 16 '16 at 15:08
1

\$\begingroup\$ could add an example (could be the same) but with unique characters (like abcde, instead 11110)? to help visualize the folding \$\endgroup\$ – Rod Nov 16 '16 at 16:24

add a comment |

Neil · Accepted Answer · 2016-11-17 21:25:50Z

Postman's Sorting

You are a postman, and you have to walk down a street, delivering letters. Odd-numbered houses are on the left, and even-numbered houses are on the right.

If you had to end up back at the beginning of the street, it would be easy: simply deliver the odd letters in ascending order and the even letters in descending order.

Instead, you need to finish at the end of the street. But you can't simply deliver the letters in ascending house number order, because you would have to cross the street so often. You need to optimise the order to minimise the number of street crossings.

Given a set of positive integers as input, your program or function should output an ordered array giving the optimal delivery sequence. You need to consider the houses in pairs: 1,2; 3,4; 5,6 etc. There are a number of cases:

If you have no letters for a pair of houses, you simply ignore them.
If you have letters for only one of a pair of houses, you have no choice, you must visit that house.
If you have letters for both houses in a pair, then you want to visit the house on the same side as the house you just visited first, then cross and visit the other house.

Example: If you have letters for houses 6, 2 and 5, then you want to deliver them in the order 2, 6, 5, so as to avoid crossing the street a second time.

[Further test cases as needed to clarify comments arising while the question is in the Sandbox.]

This is code-golf, so the shortest program wins!

Blue · Accepted Answer · 2016-11-20 12:22:33Z

Procedurally Generate a Dungeon

popularity-contest grid game generation maze

It's time to make the new Rogue!

Given no input, output a (randomly) procedurally generated dungeon with a start and an end. It must be possible to get from the start of the dungeon to the end.

Elements may include: (but are not limited to)

Key
Lock (requires key to pass)
Boss
Miniboss
Test
Reward
Multi-key
Multi-lock (requires n multi-keys to pass)
Nothing
Boolean switch - switch can toggle when inside this room
Boolean gate A - only opens when switch is off
Boolean gate B - only opens when switch is on

The output format does not matter as long as:

The types of room is present
The 2D spacial connection is present

Sandbox Notes:

Is this idea somewhat supported?
At the moment this is very unclear (at least to me). What should I add to make it more obvious what it is programs should do?
Creativity - the bane of the objective winning criteria. I hope to at least make it obvious whether an answer is valid.
Too broad? I hope not because I tried to make all dungeons solvable.
Simple answers shouldn't be upvoted and answers that output nice dungeons should be.
Should answers have to include the critical path? That might ramp up the complexity and isn't really required apart from making sure it's valid.

What is the Sandbox?

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

2661 Answers 2661

Handwriting Recognition

Conditions:

Questions for Sandbox

Gif - Jif, Jif - Gif

Rules

Examples

Largest Number Given Digits and Operators

Interleave your code with the input

Inputs and outputs

Scoring

The one-looper ASCII box

Intro

Task

The hard part

Interpret loose ranges code-golf

The challenge is the following:

Input

Output

How to win

Test cases:

Balanced Columns

Where is my error?

Examples

Spec

First 100 prime numbers in Wentelx87 code-golf

(from README)

Is this Rubik's Cube Solvable?

Implement BozoCrack

AlphaGo..olf?

Input

Output

Examples

Rules

Meta Questions

Categorize the asymptotic behavior of a consumer/producer system

Rules

Test Cases

Sandbox Notes

Examples

Fastest Cashier in the West

Format

Rules

Thoughts

It's time to parse (everything)!

Introduction

Specification

Input

Output

What to do

Warning

Who wins?

Example Input and Output

Helpful ressources

Simple Substitution Cipher Programming

Peano's quine

Match the BF output code-golf regex brainfuck

Example programs:

Specs:

Meta stuff:

Find the highest product in a grid

Absolutely correct !

The challenge

The input

Unit

Tests

How Big is the Hyperbolic Round Table of Camelot?

Assumptions:

Test Cases:

Winning Criterion:

Pay Best Card in Euchre

Objective:

Formatting

Examples

Euchre Card Strengths

Python Kolmogorov Complexity Golfer

Test Cases

Note