478
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – James Aug 29 '19 at 15:19
  • 3
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 '19 at 13:43

2844 Answers 2844

1
38 39
40
41 42
95
1
\$\begingroup\$

Fortnightly Challenge #8: A new kind of "asynchronous" KOTH

This is a placeholder for the challenge spec. You can discuss this challenge in a special chat room.


Ordinary KOTHs require that a single user take up the job of hosting the competition: running the whole competition at once by themselves. Everything is dependent on them, and they can only run so many competitions or update ever so frequently. I think this can be improved... somehow.

Here are some ideas, many of which would require an encryption scheme or something to ensure correctness.

  • Anybody can run the tournament and add their results to the current leaderboard somehow. This could be accomplished by some sort of cryptographic scheme to verify the results. Ideally the controller will be implemented via stack snippet to allow ordinary people to run it without downloading a controller.

  • When a bot is added/updated, only the new pairs of contestants should be tried, and nearly anyone can update the leaderboard by themselves. (Assuming a deterministic KOTH, which it will probably need to be in order to prevent people from simply uploading the results that occurred in their favor.)

| |
\$\endgroup\$
1
\$\begingroup\$

Chain up the cops!

Thanks to Magic Octopus Urn for the original idea!

This is a combination between a and a challenge.

Cops

Your task is to create a program that, when run in language A outputs a program, that when run in language B outputs a program which runs in language C and so on, until the final program, which outputs the string Game Over!*. You may use as many languages as you like, but each language may only be used once. Different versions of languages, or different compilers, do not count as different languages, i.e. Python 2 and Python 3 are the same language.

If using languages with different code pages, you should output the bytes that make up that program, not the characters. You should create a program that runs in at least 2 distinct languages. Languages must be free (as in beer) and be publicly available for anyone to use without paying.

Cops, you are to reveal the following things:

  • The number of languages used
  • The bytecounts of each program+
  • The code to be run in language A, but not language A

When a robber links their cracking answer, please edit this into your solution to help further robbers.

If your answer has not been completely cracked after 14 days, it is safe and you should reveal the remaining languages and the codes in said languages. The submission which is safe and uses the most amount of distinct languages wins!

Robbers

Your aim is to find out the languages the cops used. You can crack just one of the languages, or you can aim to find out the complete set of languages for any one cop, or anything in between. When cracking an answer, there are three possibilities:

  • You crack the first layer: Create a new robbers post as a Community Wiki and edit in the first solution, along with your username, in the below format. Link the post to the Cops post.
  • You crack an intermediary layer: edit your solution, and username, into the corresponding Robbers post and make sure that the cops is aware of the crack
  • You crack the final layer: Notify the cop, and edit in your crack into the Robbers post, with the notice that it is the final program and that cops' run is over.

Each robber will have a score, defined somewhat as a league table. You get one point for every layer you crack, including the start and end cracks. However, if you singlehandedly crack an answer, you get one point for each language, plus 3 points. So, if you, by yourself, crack an answer with 4 languages, you get 7 points.

Valid cracks

Meta notice: I'm having trouble deciding whether cracks have to be in the intended language or not. Thoughts?

When a robber crack a layer, they should comment below the cops post with the language, along with a way to test the current code. If the output is the same, but the language is different to the intended one, the crack is still valid (to prevent answers going in unintended directions). Obviously, if the language is correct, the crack is valid. However, a crack is only valid if the cop confirms it. I'm going to trust cops to not abuse this rule and turn down every guess and hope that the community will help deal with anyone who does.

Formatting

Cops, please format your original answer as so:

# [N] languages

    <code>

<Byte counts of the programs>

And, when a corresponding Robbers post is created and linked, please edit in

<link to Robbers post>

If your answer is safe, edit this into the title, along with the complete list of intended languages. Your program(s) can still be cracked until you do.

Robbers: Please add cracks to the correct answer in the following format, underneath previous cracks

## [N]. [Language], cracked by [username]

    <code>

<Try It Online/interpreter>

<anything else>

Where N is the current depth of the cracks. The first crack should be that same, but have

# [Cop's programs](link)

at the top of the answer.

Example

Let's walk through a quick example:

I create the following program that runs in Python:

print("""'"!revO emaG"'>o<""")

When run in Python (3), this outputs

'"!revO emaG"'>o<

This can be run in ><> and outputs

"Game Over!"

Which, when executed by Foo, outputs the desired phrase, Game Over!. All I reveal to the Robbers however, are the number of languages (3), the original code (print("""'"!revO emaG"'>o<""")) and the byte counts of the 3 submissions (30, 18 and 12).

The robbers then guess that the first language is Python, so I'd edit that in, and change the code to the output of the Python program. The next guess is Perl, which I tell them is incorrect, before they quickly guess that the answers were ><> and Foo, and my answer has been completely cracked.

My cop answer, at this point would look lien the following:

# 3 languages, [completed](link)

## Python

    print("""'"!revO emaG"'>o<""")

## ><>

    '"!revO emaG"'>o<

## Foo

    "Game Over!"

*anything else*

And the Robbers post would look like this:

# [Cop's post](link), done

## Python, cracked by user1

*code/explanation/TIO*

## ><>, cracked by user2

*code/explanation/TIO*

## Foo, cracked by user1

*code/explanation/TIO*

Meta

*: Should I change the final task? I chose the phrase as I doubt many languages have this as a builtin.

+: Thoughts on revealing the intended bytecounts? I feel as though it is a good way for robbers to verify their guesses without the cops, before commenting.

Any other questions/clarifications/dupe targets?

| |
\$\endgroup\$
  • \$\begingroup\$ So the robber who cracks the first level gets the upvotes belonging to the robbers who crack all the subsequent levels? \$\endgroup\$ – Peter Taylor Feb 15 '18 at 8:25
  • \$\begingroup\$ @PeterTaylor I had thought CW posts don't garner reputation? \$\endgroup\$ – AdmBorkBork Feb 15 '18 at 14:51
  • \$\begingroup\$ @AdmBorkBork, I missed that the robber posts were to be CW, but that's not much better. Robbers get no rep at all? I mean, sure, the incentives of fake Internet points are bad, but I'm not sure that removing them completely is an improvement. \$\endgroup\$ – Peter Taylor Feb 15 '18 at 14:55
  • \$\begingroup\$ @PeterTaylor AdmBorkBork is correct, the robbers posts are to be CW. I don't think that no rep reward will be a massive incentive for people to not compete, and if it is to them, then let them abstain. \$\endgroup\$ – caird coinheringaahing Feb 15 '18 at 16:25
  • \$\begingroup\$ I think that the final program should output a distinct phrase, and that the phrase should be given at the start as well. So if your final program outputs "Hello, world!" you'd need to state that at the start. Shouldn't limit it to Game Over! \$\endgroup\$ – Magic Octopus Urn Feb 15 '18 at 17:22
  • \$\begingroup\$ I just posted a [answer-chaining] [cops-and-robbers] sandbox draft, thinking it was an original idea, and then I scroll up the page in the Sandbox and see this... \$\endgroup\$ – Esolanging Fruit Feb 17 '18 at 21:52
  • \$\begingroup\$ "Thoughts on revealing the intended bytecounts?" I'd say that secure hashes would be better. \$\endgroup\$ – NieDzejkob Mar 5 '18 at 14:04
1
\$\begingroup\$

Generate a maximal binary Gray code

Given an input integer n, find an n-bit gray code where the sum of the absolute difference between each adjacent pair of bits converted to decimal is maximized.

For example, if n = 3, there are 96 possible gray codes, and the maximal sum of deltas in decimal of those is 21. Out of the 96 total, only 8 have maximal deltas.

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 0│0 0 1│0 1 0│0 1 1│1 0 0│1 0 1│1 1 0│1 1 1│
│1 0 0│1 0 1│1 1 0│1 1 1│0 0 0│0 0 1│0 1 0│0 1 1│
│1 1 0│1 1 1│1 0 0│1 0 1│0 1 0│0 1 1│0 0 0│0 0 1│
│0 1 0│0 1 1│0 0 0│0 0 1│1 1 0│1 1 1│1 0 0│1 0 1│
│0 1 1│0 1 0│0 0 1│0 0 0│1 1 1│1 1 0│1 0 1│1 0 0│
│1 1 1│1 1 0│1 0 1│1 0 0│0 1 1│0 1 0│0 0 1│0 0 0│
│1 0 1│1 0 0│1 1 1│1 1 0│0 0 1│0 0 0│0 1 1│0 1 0│
│0 0 1│0 0 0│0 1 1│0 1 0│1 0 1│1 0 0│1 1 1│1 1 0│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Checking the first result, the decimal values are

0 4 6 2 3 7 5 1

and the deltas of each adjacent pair are

4 2 4 1 4 2 4

and the sum of that is 21.

Rules

  • The input will be an integer n > 0.
  • You may output either one or all possible gray codes that satisfy the condition.
| |
\$\endgroup\$
  • \$\begingroup\$ Can we output the decimal values instead of the binary? \$\endgroup\$ – user202729 Feb 17 '18 at 15:18
  • 1
    \$\begingroup\$ "the sum of the absolute difference between each adjacent pair of bits converted to decimal" doesn't make much sense. Decimal is irrelevant (a number's value does not depend on its representation) and mentioning it only serves to make the sentence harder to parse. And looking at the example, it's not about adjacent pairs of bits but adjacent numbers in the sequence. \$\endgroup\$ – Peter Taylor Feb 19 '18 at 11:25
1
\$\begingroup\$

The Euler Masheroni Constant

The Euler Masheroni constant is a very interesting number. It is defined to be and appears seemingly everywhere in number theory. Famously, it is unknown whether it is rational, irrational, or transcendental.

The Challenge:

Pretty simple one here: Given N, your program should calculate the Euler Macaroni constant to at least N decimal places of prescision. Your score will be the maximum value of N for which the program is accurate, and ties will be won by the shortest code.

For refrence, the Euler Macaroni constant to 50 places is

0.57721566490153286060651209008240243104215933593992

Be sure to check out the wikipedia page for more formulas for the Oily Macaroni constant!

https://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant

| |
\$\endgroup\$
  • 4
    \$\begingroup\$ s/Macaroni/Mascheroni/g and s/Oily/Euler/g \$\endgroup\$ – Beefster Feb 19 '18 at 20:37
  • \$\begingroup\$ Mmmm. Oily Macaroni. Definitely doesn't stick together that way. \$\endgroup\$ – Beefster Feb 19 '18 at 20:50
  • \$\begingroup\$ The easy way to calculate this constant will definitely timeout for very small n, and I guess most programs will be infinite anyway. \$\endgroup\$ – user202729 Feb 20 '18 at 4:06
  • \$\begingroup\$ You can use MathJax now: $$\gamma = \lim_{n\to\infty}\left(-\ln n + \sum_{k=1}^n\frac 1 k\right)$$ \$\endgroup\$ – wastl Jun 26 '18 at 12:25
1
\$\begingroup\$

Design a language and golf its interpreter

Your task is to design a language and write an interpreter for it. Your language must have the following properties:

  • Its source code will consist of strings of two characters. I will write them as ( and ) and refer to them as parentheses, but you can choose whichever two distinct characters you like. You can choose whether to ignore other characters.

  • Valid programs will consist of any string in which the parentheses are balanced, such as ()() or (()(()())). The empty string is a valid program. You may assume the input will be a valid program.

  • Programs will take an input and return an output. Valid inputs and outputs are of the same form as source code: they must be balanced strings of parentheses. This input and output may be accomplished by any method you like, e.g. command-line arguments or STDIN/STDOUT. You may assume your program's input will always be valid.

  • Your program must be Turing complete. That means that for every computable function from balanced strings to balanced strings, there must be a program in your language that computes it. Your answer must include a proof of Turing completeness, otherwise it is not a valid answer.

This is . Your score will be the size of your interpreter's implementation, measured in bytes. The lowest score wins.

Here are some additional rules and clarifications:

  • Your interpreter must be a complete program

  • You must include a description of your language's semantics. This is needed in order to prove that it's Turing complete.

  • Your interpreter must correctly implement these semantics. (Or at least, it must be able to in principle, given infinite machine resources.) If someone finds a bug in your interpreter, your answer becomes invalid until it's fixed.

  • You may not assume numerical types are of unlimited precision unless they actually are - be careful of integer overflow!

Here is the precise grammar for programs as well as input and output strings:

<expr> ::= "(" <expr_list> ")"
<expr_list> ::= "" | <expr_list> <expr>.
<program> ::= <expr_list>

You can optionally replace the last line with

<program> ::= <expr>

which means there must always be an enclosing pair of parentheses. (So ()() and the empty string would not be valid programs, for example.) If you do this, you must do it for input and output strings, as well as programs.

As mentioned above, ( and ) may be replaced with any two distinct characters.

Sandbox notes

I've been obsessed with designing a simple and elegant language with these properties for some time, but I've never come up with one that really satisfied me. It occurred to me that "source code size of the interpreter" might work as a proxy for simplicity and elegance, so I thought I'd give this a try. Suggestions for a better winning criterion (making it a ) would be welcome.

I'd also welcome suggestions for a snappier title.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ What prevents us from trivially decoding balanced parentheses to an existing programming language, evaluating, and then encoding the result back to balanced parentheses? Try it online! \$\endgroup\$ – Adám Feb 19 '18 at 17:56
  • \$\begingroup\$ Must all strings of balanced parentheses be valid inputs and programs, or can some of them result in errors? \$\endgroup\$ – Zgarb Feb 19 '18 at 20:31
  • \$\begingroup\$ i feel like requiring the program to have to be covered in parentheses to work sort of adds an unnecessary step. i would like it if that were removed, or if it was an option whether or not it counts as invalid to have ()() etc. \$\endgroup\$ – Destructible Lemon Feb 19 '18 at 22:15
  • \$\begingroup\$ @Adám unfortunately nothing really prevents this. I'd realised that a while after posting this. I'm not sure how to resolve that currently, so I probably won't post this challenge unless I figure out a good way. \$\endgroup\$ – Nathaniel Feb 19 '18 at 23:54
  • \$\begingroup\$ @Zgarb I intended it that every balanced string is a valid program. (But one could always just return the empty string if there's an error. This is another thing I don't like but don't have an easy way to fix.) \$\endgroup\$ – Nathaniel Feb 19 '18 at 23:55
  • \$\begingroup\$ what if you had to implement the language in two distinct languages or something? actually now that i think about it, a bunch of golf languages have python eval... \$\endgroup\$ – Destructible Lemon Feb 20 '18 at 2:00
  • \$\begingroup\$ @DestructibleLemon that's not a bad idea, but the languages would need to be sufficiently different in order for it to work. I wonder how we could specify that? \$\endgroup\$ – Nathaniel Feb 20 '18 at 4:27
  • \$\begingroup\$ it might be a better idea, in fact, to go to the esolangs room, design a language, then make the challenge be implementing that. perhaps as a bonus, you could have spec options (features or syntax or something which is optional or can be from different choices, with the stipulation that the chosen version of the language has to be as functional as the normal version of the languge) \$\endgroup\$ – Destructible Lemon Feb 20 '18 at 6:40
  • 1
    \$\begingroup\$ @DestructibleLemon I really want language design to be the focus of the challenge, though. (By the way I changed the grammar spec according to your suggestion.) \$\endgroup\$ – Nathaniel Feb 20 '18 at 7:35
  • \$\begingroup\$ "Your program must be Turing complete. That means that for every computable function from balanced strings to balanced strings, there must be a program in your language that computes it" Does it? Turing completeness implies the ability to compute any computable function, but the ability to compute a subset of computable functions does not in general imply Turing completeness. \$\endgroup\$ – Peter Taylor Feb 20 '18 at 12:08
  • \$\begingroup\$ Moreover, Turing completeness doesn't say anything about representation. Minsky register machines are TM-complete, and their state could be put into bijection with balanced strings generated by the grammar <n> ::= "(" ")" | "(" <n> ")" <state> ::= <n> | <state> <n> giving a Turing-complete system which only computes computable functions from restricted balanced strings to restricted balanced strings. \$\endgroup\$ – Peter Taylor Feb 20 '18 at 12:08
  • \$\begingroup\$ "Your interpreter must correctly implement these semantics. If someone finds a bug in your interpreter, your answer becomes invalid until it's fixed. Be careful of integer overflow!" is just asking the impossible. No physical implementation can have access to unbounded memory, so strictly speaking no physical implementation can be Turing complete. \$\endgroup\$ – Peter Taylor Feb 20 '18 at 12:09
  • \$\begingroup\$ @PeterTaylor your second comment answers the question in your first comment. Do you think I should change anything or is it fine how it is? For your third comment I meant given infinite resources of course - I've amended the text. \$\endgroup\$ – Nathaniel Feb 20 '18 at 12:31
  • \$\begingroup\$ I think my second comment answers the question in my first comment in the negative, meaning that this question would incorrectly disqualify an implementation along the lines sketched in the second comment. BTW I'm pretty sure there are existing languages meeting some of these criteria, if not all, with single combinators. And if there aren't, it's a straightforward thing to do. \$\endgroup\$ – Peter Taylor Feb 20 '18 at 12:40
  • 2
    \$\begingroup\$ I can't think of an objective measure for elegance, that's fairly subjective and considering the issue Adám pointed out, code-golf won't do very well. What's your reasons against making it a popcon? \$\endgroup\$ – ბიმო Feb 20 '18 at 19:19
1
\$\begingroup\$

Find Graph Isomorphism

Meta:

I don't know whether there are any known algorithms for solving this problem, that also means I'm not sure whether this is an interesting challenge. EDIT: Ok it is probably equally hard as the graph isomorphism problem.

Inspired by this puzzle

Given two isomorphic directed (unweighted) graphs with labelled nodes, find an isomorphism between the two graphs.

Details

  • You have to provide a working implementation of your algorithm.
  • You have to provide the complexity expressed in the number of nodes, edges (or possibly other numbers?)
  • The graphs can be represented as an adjecency matrix, as set of pairs that represent edges, as an adjecency list or as a native graph type etc.
  • The output can be a function that maps the labels of one graph to the labels of the other, as a list as a graph etc.
  • If necessary, you can assume that there are no edges with the same start as end node.

Examples

to be added...

| |
\$\endgroup\$
  • \$\begingroup\$ (What if it's unknown-complexity? Some heuristics can be quite fast in practice but formally reason about the complexity can be very hard) \$\endgroup\$ – user202729 Feb 22 '18 at 2:31
1
\$\begingroup\$

Assemble an XOISC program

Tags: , ,


Recently I solved this challenge, for which I created XOISC - a very low-level functional language. To compile a program (written in the absurdly high-level lambda calculus programming language) it must first be translated into an expression consisting only of X combinators and from there it can be translated to the "machine language".

There's an initially empty stack and the program only consists of a stream of integers. For each integer the following happens:

Pop N elements f1,...,fN and push X (f1 (..(fN-1 fN)..)) - ie. it right-folds function application and applies this to another X.

Eventually we'll end up with a stack of functions which gets left-folded with function application. That's it.

How does it work?

When parsing such an expression, one thing to keep in mind is that function application is left-associative - meaning that X (X X) X is read as (X (X X)) X rather than X ((X X) X).

If we have an expression f g with sub-expressions f and g (in the code below App f g - eg. X (X X) X would be f = X (X X) and g = X), there's a simple recursive algorithm to assemble it:

-- Base case: We simply need to pop the accumulated functions 
asm' n X         = [n]
-- Recurse: First build the left function, then the right one. 
--          Incrementing n ensures that we leave (f g) on stack
asm' n (App f g) = asm' 0 f ++ asm' (n+1) g

-- Now we start with 0 functions on the stack:
asm expr = asm' 0 expr

For those unfamiliar with Haskell:

  • this algorithm assumes an already parsed expression in the form of of a binary tree (the definition of the data structure would be data Exp = X | App Exp Exp where X would be a leaf and App f g would be a node with children f and g that are Exps as well)*
  • asm' n exp does a case distinction by matching a pattern on exp:
    • if the expression is X (ie. exp = X) it's the base case and just returns a singleton list containing n (an integer)
    • else it's of the form f g (with f,g some sub-expressions) which is expressed as App f g, so it will recursively build the list for f and append the list of g
  • to assemble an expression exp we begin initialize the recursive algorithm with n = 0 (asm' 0 exp)

Note: Since a lot of people here know Python, you can find a horrible but very well documented Python reference implementation here which does the parsing as well as the assembling!


* The | means that an Exp type can be constructed of either the left constructor (X) or of the right one (App Exp Exp where the two Exp are Exp two sub-expressions).

For example the expression X (X X) X would be expressed as App (App X (App X X)) X.

Example

Having an expression X (X X) X, it helps to think of the implicit parentheses: (X (X X)) X

Translating this with the above algorithm:

  • Assemble (X (X X)):
    • Assemble X:
      • Base case => 0
    • Now Assemble X X, making sure it gets applied to the previous one (+1)
      • The first X gives us a 0
      • The second one gives us 0 + 1 + 1 = 2 (apply to X and previous one)
  • So the left (X (X X)) gave us [0,0,2], assembling the right X:
    • This gives us 0 + 1 (apply to the previous one)

And we end up with the program [0,0,2,1].

Note: While this algorithm ensures that there's a program for every expression, there can be other solutions too. For example [0,0,1,0] would be a valid one for X (X X) X as well.

Challenge

Given an expression consisting of X combinators, translate it to the XOISC machine language:

  • Input will be a string encoding such an expression
    • The input will be a valid expression and non-empty
    • You may choose to require an input string that contains no spaces
    • You may choose the characters encoding parentheses and the combinator itself (as long as it's consistent, eg. using [,],x instead of (,),X)
    • You're guaranteed that there are no unnecessary parentheses (eg. (X X) X would result in undefined behaviour)
  • Output can be a list of integers, a string separated by new-lines or whitespaces

Testcases

These testcases assume that the input contains whitespaces and choose X to encode the combinator.

Note that there may be multiple valid outputs, you're free to choose one* - I'll only show the solution resulting from the above algorithm:

X -> [0]
X X X -> [0,1,1]
X (X X) -> [0,0,2]
X (X X) X -> [0,0,2,1]
X (X (X (X X X))) -> [0,0,0,0,1,4]
X (X X) (X X) (X X) -> [0,0,2,0,2,0,2]
X (X X X (X X)) -> [0,0,1,1,0,3]
X (X (X X) (X X)) -> [0,0,0,2,0,3]
X X (X X (X (X (X (X (X X X)))) X) X) -> [0,1,0,1,0,0,0,0,0,1,5,2,2]
X (X (X X) X (X X X)) X (X (X (X X) X)) -> [0,0,0,2,1,0,1,3,1,0,0,0,2,3]
X (X (X (X (X X) X X) X X X) X X X X) X X X X X -> [0,0,0,0,0,2,1,2,1,1,2,1,1,1,2,1,1,1,1,1]
X (X (X X (X X) (X X) (X X) X) X (X X) X) X (X X X) X -> [0,0,0,1,0,2,0,2,0,2,2,1,0,2,2,1,0,1,2,1]

* Here's a program to validate alternative solutions

Sandbox

  • I already posted this to main, but apparently I did a bad job of explaining it.. It's hard to tell what's missing, I'd be happy for feedback (feel free to edit this)!
| |
\$\endgroup\$
  • \$\begingroup\$ I think you need to move away from Haskel syntax and jargon. Just as one example: I have no idea what the point of "Having an expression X (X X) X, it helps to think of the implicit parentheses: (X (X X)) X" is. The whole explanation seems reliant on an understanding of concepts I personally don't usually think about. Also it's confusing having an example as code that is only thinking about the problem in one way and outputting only a single solution of many possible while trying to understand what the possibilities are. Since I can't understand it it is hard for me to help make it clearer :( \$\endgroup\$ – Jonathan Allan Feb 23 '18 at 22:12
  • \$\begingroup\$ @JonathanAllan: Thanks a lot for the feedback! It's not necessarily Haskell jargon, but I think I see what you mean. I'll rewrite this completely, it's probably the easiest way. \$\endgroup\$ – ბიმო Feb 23 '18 at 22:22
1
\$\begingroup\$

Convert Arabic Numbers to Chinese Numbers

There EXISTS a similar question, "Convert Chinese numbers", but the question itself differs from that question by:

  1. That question asks for a shortest code converting Chinese numbers to Arabic numbers, but this asks for a shortest code converting in the opposite direction.
  2. That question limits the range of 1 <= N < 10^3, but this has the range far larger than that -- 1 <= N < 10^8192.
  3. Due to the range of that question, that question only considers one type of representation on Chinese numbers, but this considers four -- the commonly used Wan Jin (萬進) and other ancient systems. These terms will be explained in the introduction part.

There EXISTS another similar question "Convert a number to Korean", but there is essential difference because Korean number only uses Wan Jin, always omits "一(일)"s before "十(십)"s, "百(백)"s and "千(천)"s and all "零"s between digits, and so does Japanese.

Sandbox

  • I have edited the challenge description so that the rules are now outlining the process of conversion. Although this will be clearer in illustrating the rules, will this be restricting the choice of algorithms?

Introduction

Chinese numbers, literally, is the number still in use in societies which uses Chinese characters. Although Arabic numbers are also in use nowadays, Chinese numbers still have an important role.

The system Chinese people in Taiwan are using is called Wan Jin (萬進), which names 1,000,000,000,000 (1 trillion) as Yi Zhao (一兆). However, according to Wu Jing Suan Shu (五經算術) ,in the history there existed 3 different kinds of such large-number representations. The reference says:

按黃帝為法,數有十等。及其用也,乃有三焉。十等者,謂「億、兆、京、垓、秭、壤、溝、澗、正、載」也。三等者,謂「上、中、下」也。其下數者,十十變之。若言十萬曰億,十億曰兆,十兆曰京也。中數者,萬萬變之。若言萬萬曰億,萬萬億曰兆,萬萬兆曰京也。上數者,數窮則變。若言萬萬曰億,億億曰兆、兆兆曰京也。

(Translation) According to Huang Di, there are 10 "ranks" of numbers. Regarding the usages, there are three. The 10 ranks are called (億), Zhào (兆), Jīng (京), Gāi (垓), (秭), Ráng (穰), Gōu (溝), Jiàn (澗), Zhèng (正), Zài (載). The three usages are called "Upper", "Middle" and "Lower". For the "Lower", the rank changes if multiplied by 10. We call 10 Wàn as , 10 as Zhào, and 10 Zhào as Jīng. For the "Middle", the rank changes if multiplied by 100,000,000. We call 100,000,000 Wàn as , 100,000,000 as Zhào, and 100,000,000 Zhào as Jīng. And for the "Upper", the rank changes if the rank exhausts its numbers. We call 1 Wàn Wàn as , 1 as Zhào, and 1 Zhào Zhào as Jīng.

To sum up, we have 4 systems which is, or was in use in Chinese history:

  • Xia Shu (下數): Starting from wan (萬, 10,000), the rank changes by multipling by 10. 10 wan is called yi (億, 100,000), 10 yi is called zhao (兆, 1,000,000), 10 zhao is called jing (京, 10,000,000), etc.
  • Zhong Shu (中數): Starting from wan (萬, 10,000), the rank changes by multipling by 108, with the exception of yi, which represents 10^8. 10,000 wan is called yi (億, 10^8), 108 yi is called zhao (兆, 10^16), 108 zhao is called jing (京, 10^24), etc.
  • Shang Shu (上數): Starting from wan (萬, 10,000), the rank changes by squaring. 10,000 wan is called yi (億, 10^8), 108 yi is called zhao (兆, 10^16), 1016 zhao is called jing (京, 10^32), etc.
  • Wan Jin (萬進): Starting from wan (萬, 10,000), the rank changes by multipling by 10,000. 10,000 wan is called yi (億, 10^8), 10,000 yi is called zhao (兆, 10^12), 10,000 zhao is called jing (京, 10^16), etc.

Table 1: Rank markers in Chinese numbers

 Name    Wan Jin      Xia Shu      Zhong Shu   Shang Shu
(十               commonly representing 10^1            )
(百               commonly representing 10^2            )
(千               commonly representing 10^3            )
(萬               commonly representing 10^4            )
 億      10^8         10^5         10^8        10^8
 兆      10^12        10^6         10^16       10^16
 京      10^16        10^7         10^24       10^32
 垓      10^20        10^8         10^32       10^64
 秭      10^24        10^9         10^40       10^128
 穰      10^28        10^10        10^48       10^256
 溝      10^32        10^11        10^56       10^512
 澗      10^36        10^12        10^64       10^1024
 正      10^40        10^13        10^72       10^2048
 載      10^44        10^14        10^80       10^4096

For numbers smaller than 10, this works as

零:0 一:1 二:2 三:3 四:4 五:5 六:6 七:7 八:8 九:9

Challenge

In this challenge, you are required to write the shortest code, accepting two inputs: the number N, and a number S indicating the system used, converts N into the corresponding Chinese representation according to the given system, and output the representation. Here are some basic rules about converting Chinese numbers:

For numbers less than 10,000 and Xia Shu numbers:

  1. Append position markers digit by digit first.
    • 1234 => 一千二百三十四
    • 1234567 => 一兆二億三萬四千五百六十七
  2. Strip away all position markers prepended by "零", coalesce all consecutive "零"s into a single "零", and remove the leading/trailing "零"s.
    • 5 => 五, 25 => 二十五, 125 => 一百二十五
    • 20 => 二十, 100 => 一百, 5000 => 五千.
    • 1001 => 一千零一

For Wan Jin numbers:

  1. Divide the digits into subgroups of at most 4 digits each from the right.
    • 12345678900004321 => 1'2345'6789'0000'4321
  2. Apply to each subgroup the conversion for numbers less than 10,000 (as above), and append each subgroup with the corresponding rank markers. If there is any "0" at the subgroup boundary, append "零" after the rank marker.
    • 1'2345'6789'0000'4321 => (一)京(二千三百四十五)兆(六千七百八十九)億零(零)萬零(四千三百二十一)
  3. Discard the subgroups with "零", together with their rank markers, and remove redundant "零"s.
    • (一)京(二千三百四十五)兆(六千七百八十九)億零(零)萬零(四千三百二十一) => 一京二千三百四十五兆六千七百八十九億零四千三百二十一

For Zhong Shu numbers:

  1. Divide the digits into subgroups of at most 8 digits each from the right.
    • 12345678900004321 => 1"23456789"00004321
  2. Apply to each subgroup the conversion for Wan Jin numbers (as above), and append each subgroup with the corresponding rank markers. If there is any "0" at the subgroup boundary, append "零" after the rank marker.
    • 1"23456789"00004321 => (一)兆(二千三百四十五萬六千七百八十九)億零(四千三百二十一)
  3. Discard the subgroups with "零", together with their rank markers, and remove redundant "零"s.
    • (一)兆(二千三百四十五萬六千七百八十九)億零(四千三百二十一) => 一兆二千三百四十五萬六千七百八十九億零四千三百二十一

For Shang Shu numbers:

  1. Divide the digits into 2 subgroups: the least significant one with number of digits equals to the least power of 2 not less than half of the original length, and the most significant one with the remaining digits.
    • 123456789012345678901234567890 => (12345678901234)(5678901234567890)
  2. Append the most significant subgroup with the corresponding rank marker. If there is any "0" at the subgroup boundary, append "零" after the rank marker.
    • (12345678901234)(5678901234567890) => 12345678901234兆5678901234567890
  3. Discard the subgroups with "零", together with their rank markers
  4. Recursively apply all steps to each subgroup with a lower rank marker, until the number of digits in a subgroup is less than 4, which then apply the conversion for numbers less than 10,000 (as above).
    • 12345678901234兆5678901234567890 => 123456億78901234兆56789012億34567890 => 12萬3456億7890萬零1234兆5678萬9012億3456萬7890 => 十二萬三千四百五十六億七千八百九十萬零一千二百三十四兆五千六百七十八萬九千零一十二億三千四百五十六萬七千八百九十

And at last...

  1. If "一十" is at the beginning, remove the "一".
    • 15 => 十五
    • 114514 => 十一萬四千五百一十四, 10011 => 一萬零一十一.
  2. Remove redundant "零"s, and if an empty string occurs, return with "零".

For more details, the reference implementation in JSFiddle gives the reference code.

Requirements

  • Your code must be a full program or a function. Defining helper functions are allowed. Snippets are not allowed.
  • Standard loopholes are not allowed by default.
  • You can use any methods of I/O that are considered "standard" by PPCG community.
  • You must receive 2 inputs, one number N, and one number S. You can pass the inputs as strings or as integers. Please indicate your choice.
  • You may assume the input is always valid, i.e. S in [0, 1, 2, 3] and N is within the corresponding range:

Table 2: Number systems and their representable number range

S (System)       N (Number Range)
0 (Wan Jin)      1 <= N < 1E+48
1 (Xia Shu)      1 <= N < 1E+15
2 (Zhong Shu)    1 <= N < 1E+88
3 (Shang Shu)    1 <= N < 1E+8192
  • In case Unicode is not supported by the interpreter and/or the language, or for any reasons, you may use one of the two Chinese Pinyins in place of the corresponding Chinese characters as output as follows. Your choice must be consistent over all outputs. One space must be added between the pinyins of 2 characters. You must indicate if you choose to do so.

Table 3: The Chinese characters and their pinyin representations

Character  Pinyin              Character  Pinyin
一         yī or yi1           二         èr or er4
三         sān or san3         四         sì or si4
五         wǔ or wu3           六         liù or liu4
七         qī or qi1           八         bā or ba1
九         jiǔ or jiu3         十         shí or shi2
百         bǎi or bai3         千         qiān or qian1
萬         wàn or wan4         億         yì or yi4
兆         zhào or zhao4       京         jīng or jing1
垓         gāi or gai1         秭         zǐ or zi3
穰         ráng or rang2       溝         gōu or gou1
澗         jiàn or jian4       正         zhèng or zheng4
載         zài or zai4         零         líng or ling2

Example I/O (Only the first Pinyin format is displayed)

In these examples, I use ' => 萬, " => 億, (...) => 兆, [...] => 京, {...} => 垓, <...> => 秭 in the grouping for clarity. The grouping is only for illustration, and you do not need to print the groupings.

Input:    18446744073709551616 0
Grouping: [1844](6744)0737"0955'1616
Output:   一千八百四十四京六千七百四十四兆零七百三十七億零九百五十五萬一千六百一十六
    or    yī qiān bā bǎi sì shí sì jīng liù qiān qī bǎi sì shí sì zhào líng qī bǎi sān shí qī yì líng jiǔ bǎi wǔ shí wǔ wàn yī qiān liù bǎi yī shí liù

Input:    1234567890 1
Grouping: <1>{2}[3](4)5"6'7890
Output:   一秭二垓三京四兆五億六萬七千八百九十
    or    yī zǐ èr gāi sān jīng sì zhào wǔ yì liù wàn qī qiān bā bǎi jiǔ shí

Input:    1267650600228229401496703205376 2
Grouping: [126'7650](6002'2822)9401'4967"0320'5376
Output:   一百二十六萬七千六百五十京零六千零二萬二千八百二十二兆九千四百零一萬四千九百六十七億零三百二十萬零五千三百七十六
    or    yī bǎi èr shí liù wàn qī qiān liù bǎi wǔ shí jīng líng liù qiān líng èr  wàn èr qiān bā bǎi èr shí èr zhào jiǔ qiān sì bǎi líng yī wàn sì qiān jiǔ bǎi liù shí qī yì líng sān bǎi èr shí wàn líng wǔ qiān sān bǎi qī shí liù

Input:    8749002899132047697490008908470485461412677723572849745703082425639811996797503692894052708092215296 3
Grouping: {[8749](0028'9913"2047'6974)9000'8908"4704'8546}[(1412'6777"2357'2849)7457'0308"2425'6398](1199'6797"5036'9289)4052'7080"9221'5296
Output  : 八千七百四十九京零二十八萬九千九百一十三億二千零四十七萬六千九百七十四兆九千萬零八千九百零八億四千七百零四萬八千五百四十六垓一千四百一十二萬六千七百七十七億二千三百五十七萬二千八百四十九兆七千四百五十七萬零三百零八億二千四百二十五萬六千三百九十八京一千一百九十九萬六千七百九十七億五千零三十六萬九千二百八十九兆四千零五十二萬七千零八十億零九千二百二十一萬五千二百九十六
    or    bā qiān qī bǎi sì shí jiǔ jīng líng èr shí bā wàn jiǔ qiān jiǔ bǎi yī shí sān yì èr qiān líng sì shí qī wàn liù qiān jiǔ bǎi qī shí sì zhào jiǔ qiān wàn líng bā qiān jiǔ bǎi líng bā yì sì qiān qī bǎi líng sì wàn bā qiān wǔ bǎi sì shí liù gāi yī qiān sì bǎi yī shí èr wàn liù qiān qī bǎi qī shí qī yì èr qiān sān bǎi wǔ shí qī wàn èr qiān bā bǎi sì shí jiǔ zhào qī qiān sì bǎi wǔ shí qī wàn líng sān bǎi líng bā yì èr qiān sì bǎi èr shí wǔ wàn liù qiān sān bǎi jiǔ shí bā jīng yī qiān yī bǎi jiǔ shí jiǔ wàn liù qiān qī bǎi jiǔ shí qī yì wǔ qiān líng sān shí liù wàn jiǔ qiān èr bǎi bā shí jiǔ zhào sì qiān líng wǔ shí èr wàn qī qiān líng bā shí yì líng jiǔ qiān èr bǎi èr shí yī wàn wǔ qiān èr bǎi jiǔ shí liù

Here is a reference implementation in JS, not golfed at all

Winning Criteria

As this is a , so shortest code measuring in bytes wins. Accented Latin alphabets and Chinese characters must be measured in UTF-8 unless they are included in the SBCS of the language and can be used in the string literals.

Reference

Wikipedia - 中文數字

| |
\$\endgroup\$
  • \$\begingroup\$ I think you should also add an explanation for numbers less than 10,000. What's even 1, 2, 3, ...? \$\endgroup\$ – wastl Feb 25 '18 at 19:25
  • \$\begingroup\$ @wastl Added back details about 0~9. For numbers less than 10,000, Xia Shu algorithm applies \$\endgroup\$ – Shieru Asakoto Feb 26 '18 at 3:06
  • \$\begingroup\$ no example for coalesce all consecutive "零"s into a single "零", e.g. 4002 \$\endgroup\$ – tsh Feb 26 '18 at 3:56
  • \$\begingroup\$ what is the result of WanJin(10010)? 一萬零一十? 一萬零十? \$\endgroup\$ – tsh Feb 26 '18 at 3:59
  • \$\begingroup\$ @tsh Added. and WanJin(10010) should be 一萬零一十 because the 一十 is not at the beginning. (一萬零十 should be something in like dialect?) There is an example of WanJin(10011) though \$\endgroup\$ – Shieru Asakoto Feb 26 '18 at 4:00
  • \$\begingroup\$ @user71546 The example is for XiaShu(10011), not WanJin(10011). \$\endgroup\$ – tsh Feb 26 '18 at 4:02
  • \$\begingroup\$ Oh I should indicate that the replacement is only at the final step. \$\endgroup\$ – Shieru Asakoto Feb 26 '18 at 4:06
  • \$\begingroup\$ @tsh Grouped the removal of redundant "零"s and removal of leading "一" before "十" at the very end. \$\endgroup\$ – Shieru Asakoto Feb 26 '18 at 4:10
1
\$\begingroup\$

Build a cardinal cyclic quine

A cardinal cyclic quine is a cyclic quine with four states, one for each orientation of the cardinal directions.

See also Build a half cardinal cyclic quine and Take a stand against long quine lines.

Rules

You can decide which rotation you want to implement, clockwise or counter-clockwise.

Once rotated, any gaps in your code should be replaced with spaces to preserve the positioning.

Each program must be unique, you cannot use a quine that has the same layout regardless of orientation.

Your program must satisfy the community definition of a quine.

This is so the shortest program in each language wins. Your first program is used for your byte count.

Standard loopholes are forbidden.

Examples

If your program is:

$_=q{print};eval

Then the next iterations must be either:

$
_
=
'
p
r
i
n
t
'
;
e
v
a
l

lave;}tnirp{q=_$

l
a
v
e
;
'
t
n
i
r
p
'
=
_
$

or

l
a
v
e
;
'
t
n
i
r
p
'
=
_
$

lave;}tnirp{q=_$

$
_
=
'
p
r
i
n
t
'
;
e
v
a
l

Or if your program is:

;$_=';
;$_=';
print

Then the next iterations must be either:

;;
''t
==n
__i
$$r
;;p

;'=_$;
;'=_$;
 tnirp

p;;
r$$
i__
n==
t''
 ;;

or:

p;;
r$$
i__
n==
t''
 ;;

;'=_$;
;'=_$;
 tnirp

;;
''t
==n
__i
$$r
;;p

| |
\$\endgroup\$
  • \$\begingroup\$ Hope that the source is not a one-line palindrome (specifically, not a palindrome constructed by padding the source with comments) \$\endgroup\$ – Weijun Zhou Feb 28 '18 at 21:38
  • \$\begingroup\$ ^ Yeah you might want to prevent this by requiring all four programs to be different. \$\endgroup\$ – Martin Ender Feb 28 '18 at 21:40
  • \$\begingroup\$ @MartinEnder I guess my comments here apply to the open question too, but a palindrome with comments probably wouldn't be an optimal solution, so I'm not sure about banning that. I feel that might exclude many languages in which this challenge wouldn't otherwise be possible. Do you think banning them is for the best for the challenge? Can you forsee low-effort answers without banning them? \$\endgroup\$ – Dom Hastings Mar 1 '18 at 8:51
  • \$\begingroup\$ @WeijunZhou ^^ :) \$\endgroup\$ – Dom Hastings Mar 1 '18 at 8:51
  • \$\begingroup\$ Those cases may be just as well submitted to your existing challenge of half cardinal cyclic quine, and copying answers from your existing challenge to this one is no fun. \$\endgroup\$ – Weijun Zhou Mar 1 '18 at 9:03
  • \$\begingroup\$ @WeijunZhou Of course. Ok, since that stipulation wasn't added to the original, I'll ensure that's added to this one. Thanks for taking the time to check this out! \$\endgroup\$ – Dom Hastings Mar 1 '18 at 9:23
1
\$\begingroup\$

Safely check a password against HIBP v2 range API

Per https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/, what would be the shortest code to safely check a password against the Have I Been Pwned? k-anonymity (range) API, as mentioned in the article?

API overview

Specifically, the API is at:

https://api.pwnedpasswords.com/range/$FIRST_5_CHARS_OF_SHA1

and returns a list of SHA1 hashes beginning with the specified 5 chars (more precisely: it returns only the substrings of hashes after $FIRST_5_CHARS_OF_SHA1).

For example, given a password P@ssw0rd, its SHA1 hash is:

21BD12DC183F740EE76F27B78EB39C8AD972A757
\---/\---------------------------------/
  |                     |
  `-- first 5 chars     `-- rest of chars

and thus for a request like one of below:

https://api.pwnedpasswords.com/range/21BD1
https://api.pwnedpasswords.com/range/21bd1

the API gives a response like below (... represents more lines):

...
29B59205F57C2608CAE47E8157621FF7645:1
2B766777053A89201D8257221BBC161E279:2
2D10A6654B6D75908AE572559542245CBFA:2
2D6980B9098804E7A83DC5831BFBAF3927F:1
2D8D1B3FAACCA6A3C6A91617B2FA32E2F57:1
2DC183F740EE76F27B78EB39C8AD972A757:47205
2DE4C0087846D223DBBCCF071614590F300:2
2DEA2B1D02714099E4B7A874B4364D518F6:1
2E90B7B3C5C1181D16C48E273D9AC7F3C16:1
2EAE5EA981BFAF29A8869A40BDDADF3879B:1
2F1AC09E3846595E436BBDDDD2189358AF9:1
...

Existence of 2DC183F740EE76F27B78EB39C8AD972A757 in the response means that P@ssw0rd was found in some breach and should be considered unsafe. Number 47205 signifies how many times such a password occurs in all the contributing breaches.

Rules details

  • The password must be read from user's keyboard. Per the next rule, it should not be displayed on screen, thus if read from standard input, usually the "character echo" would need to be disabled (e.g. read -s in bash). If implemented as a GUI app, e.g. a standard "password input" widget may be used, which would replace typed characters with asterisks or black dots.
  • "Safely" means that the solution should not leak raw password to other users of a machine (e.g. the raw password should never appear as part of command line of any subcommand, and should never appear on screen) or outside the machine (websites, etc.). The full hash should not be shared outside the machine either.
    • Specifically, it must be clear (for an experienced user of the language) from the code comprising the solution that the raw password (and the SHA) do not leak (as mentioned above). So, for example, the solution's code cannot be downloaded from a remote repository (not sure if it's already included in default forbidden loopholes list).
  • The SHA sum of the checked password should be printed on screen, to make it possible to verify correctness of the solution, e.g. by checking SHA sum for P@ssw0rd. Other hashes can be printed too or not, but the one matching the checked password must be easy to see (i.e. always first/last/highlighted/...)
  • The solution should also display the number of occurrences of the password "in the wild" as returned by the API (i.e. 47205 for P@ssw0rd).
  • The solution should print at least a 1 character of prompt before reading the answer, so that user knows console is safely in "no echo" mode.

Extra tag

To keep with the site's sport spirit, I'm putting no formal restrictions on language. However, personally I'm particularly interested in and curious about "real-world usable" answers. As such, if your answer has the following "extra" attributes:

  • can be typed in bash as a one-liner (with appropriate preamble like perl -ne if needed)
  • is composed only of printable ASCII characters (no Unicode)

please append an extra marker/tag like below in the "title" line of your answer:

[bash oneliner: 30 +7]

where 30 is the length of the actual code in your preferred language, and +7 is the length of the required preamble/postamble. For pure bash answers, this can be +0. Please then also include the actual oneliner, together with the preamble/postamble.

As an explanation, the benefits of a one-liner I'm interested in for "real world users", are such that a one-liner is easy to re-type and execute in console for paranoid users, who would prefer to do it instead of Ctrl-C & Ctrl-V.


Sample naive answer in bash

Split to multiline with \s purely for readability:

$ (sha=$(IFS= read -s -p "pwned? " pw; tr -d '\n' <<<$pw | shasum ); \
  curl -s https://api.pwnedpasswords.com/range/${sha:0:5} | \
  (grep -i ${sha:5} || echo "${sha:5}:0") | \
  sed "s/^/${sha:0:5}/")
pwned? 21bd12DC183F740EE76F27B78EB39C8AD972A757:47205

One-liner:

$ (sha=$(IFS= read -s -p "pwned? " pw; tr -d '\n' <<<$pw | shasum ); curl -s https://api.pwnedpasswords.com/range/${sha:0:5} | (grep -i ${sha:5} || echo "${sha:5}:0") | sed "s/^/${sha:0:5}/")
pwned? 21bd12DC183F740EE76F27B78EB39C8AD972A757:47205
| |
\$\endgroup\$
  • 2
    \$\begingroup\$ By the way -- Welcome to PPCG, and thanks for using the sandbox and understanding the site guidelines! \$\endgroup\$ – user202729 Mar 1 '18 at 13:38
  • \$\begingroup\$ (to be self-contained, you should also briefly explain what the API does) \$\endgroup\$ – user202729 Mar 1 '18 at 13:59
  • \$\begingroup\$ @user202729 Sure, you can; but this loses the usability benefits of it being a one-liner, such as easy re-typing and easy immediate execution. Arguably removing the request (and restriction) for "one-liner" is similar in spirit to removing request for "as few characters as possible"/"code-golf". I.e. why even bother with any request... \$\endgroup\$ – akavel Mar 1 '18 at 15:06
  • \$\begingroup\$ Then how do you define one-liner? Doesn't have any 0x0A char? Doesn't have any 0x0D char? Doesn't have any char in that code-page that is used for line feed? What if a programming language uses a code page without any line-feed character? What if a language uses a code page where the newline can be replaced by other character? \$\endgroup\$ – user202729 Mar 1 '18 at 15:37
  • 1
    \$\begingroup\$ I tried to modify the question to mention "bash one-liner" only as an "extra", non-required attribute, but asking for it to be clearly labeled. I also removed most of my previous comments to de-noise the conversation. \$\endgroup\$ – akavel Mar 1 '18 at 16:02
  • 3
    \$\begingroup\$ Why restrict the input to stdin or tty? Any special reasons here that do not accept a GUI version answer? \$\endgroup\$ – tsh Mar 2 '18 at 5:33
  • \$\begingroup\$ @tsh Good question and good idea. My intention was to focus on requiring "no echo", but now I look at it I see I didn't convey that well. I'll try to edit this, though I feel it may be tricky. And also add your idea about GUI, absolutely an oversight on my side. Hm, if you'd have some ideas how to better express this, I'm absolutely interested! \$\endgroup\$ – akavel Mar 2 '18 at 17:31
  • \$\begingroup\$ @tsh Uh, and I forgot to say the most important thing: Thanks! :) \$\endgroup\$ – akavel Mar 2 '18 at 17:40
  • \$\begingroup\$ ... would reading from a file that other users don't have access considered safe? \$\endgroup\$ – user202729 Mar 8 '18 at 3:39
  • \$\begingroup\$ @user202729 "The password should be read from user's keyboard" is important for me, so reading from a file is not allowed. Should I change the "should" to "must" to make it clear? \$\endgroup\$ – akavel Mar 8 '18 at 9:45
  • \$\begingroup\$ Looks good. As it's observable whether the SHA/raw password leak (just check what the computer sent to the internet and see if the password is there), the "specifically..." part doesn't seem necessary. \$\endgroup\$ – user202729 Mar 8 '18 at 11:21
1
\$\begingroup\$

Image to HTML ASCII-Art


Given an input image n, output each pixel as a 0 using HTML for coloring and <br/> as a delimiter for the rows.


Example:

Input Image:

Input Image 1

Example HTML Output: https://pastebin.com/jDHZwb4P

Rendered Output:

Output rendered as HTML...


Rules:

  • You may color the 0's using any HTML trick you know of (CSS Style, JavaScript, etc)...
  • You may use any character other than 0 that shows visible color if you so wish.
  • Colors must be exact down to the RGB of the pixel, alpha can be assumed non-existent.
  • If you get a malformed image, or an image with transparency, you may error.
  • This is , lowest byte-count wins.
| |
\$\endgroup\$
  • \$\begingroup\$ I think you should specify the image format and IO much more. For example PPM would be much easier compared to PNG (example image) or other image formats. Does the full [insert format here]-specification need to be supported? What kind of input (eg. string/bytestring, filename, url,...)? What about the output, does it need to be valid HTML or does successfully rendering with ABC-browser (version XYZ) count? \$\endgroup\$ – ბიმო Mar 13 '18 at 23:43
  • \$\begingroup\$ @bmo good ideas on all fronts. Im on mobile but Ill make updates. I was expecting a this is a dupe comment though tbh. \$\endgroup\$ – Magic Octopus Urn Mar 13 '18 at 23:59
  • \$\begingroup\$ Wanted to leave it open as much as possible. Just anything that can be rendered by a browser as colored text from an image, but Isee no reason to disallow personal browser specifications. Like i could see some dumb IE5 trick to render text being neat as long as they explain it. \$\endgroup\$ – Magic Octopus Urn Mar 14 '18 at 0:17
  • \$\begingroup\$ Can we use a space instead of 0? \$\endgroup\$ – user202729 Mar 14 '18 at 8:34
  • \$\begingroup\$ @user202729 Of course! Wait... no, good point. \$\endgroup\$ – Magic Octopus Urn Mar 14 '18 at 12:44
  • \$\begingroup\$ Why should we assume alpha is nonexistent when the opacity property exists? \$\endgroup\$ – RamenChef Mar 15 '18 at 11:55
  • \$\begingroup\$ @RamenChef For simplicity sake. \$\endgroup\$ – Magic Octopus Urn Mar 15 '18 at 12:09
1
\$\begingroup\$

Find most isolated point

Given a finite set S of points in d dimensions, find the most isolated points, that is the point with the greatest distance to its closest neighbours.

Or more mathematically, the point p ∈ S that maximizes min {d(p,q) | q ∈ S, q ≠ p}.

Details

  • You can return the coordinates of the actual point, or you can alternatively return the index of the point in the input list.
  • The most isolated point as defined above is not necessarily unique. But you can assume that the given input results in an unique such point.

Examples

1D:

  • [0,1] (invalid, no unique result)
  • [0,1,3] -> 3,

2D:

  • [(0,0),(0,1),(1,2)] -> [(1,2)]

more to be added...

This challenge was inspired by this question. If you find a particularly time-efficient solution please post it there!

| |
\$\endgroup\$
1
\$\begingroup\$

Implement RaGOL

RaGOL (Random Game of Life) is a randomized cellular automaton based on GOL (Game of Life). For reference, here are the rules of GOL (B3/S23):

  • Moore neighborhoods are used, that is, a cell # looks at its neighbors * as in here:

    .......
    .......
    ..***..
    ..*#*..
    ..***..
    .......
    .......

  • A cell can have 2 states: dead or alive

  • If a dead cell has 3 alive neighbors, it becomes alive.
  • If an alive cell does not have exactly 2 or 3 alive neighbors, it becomes dead.

In this challenge, we will assume the board is unbounded, and the default state of a cell is dead.

However, since we have already implemented GOL, it's time to change the rules a bit. Here are the differences between GOL and RaGOL:

  • If a dead cell has 3 alive neighbors, there is 1/3 of a chance it becomes alive.
  • If an alive cell has 2 alive neighbors, there is 1/5 of a chance it becomes dead.
  • If an alive cell has 3 alive neighbors, there are 2/5 of a chance it becomes dead.

Note that if an alive cell doesn't have exactly 2 or 3 alive neighbors, it still becomes dead just like in GOL.

Challenge

Your challenge is to get an x×y RaGOL board B where x > 0 and y > 0 and a number N > 0 and return the board after N generations starting from B.

Please note that the result isn't deterministic.

You will also need to expand the board to simulate an unbounded-board automaton in some cases.

Rules

  • You can get B and N in any reasonable way.
  • Errors due to floating-point imprecision do not matter, be it a slight difference due to how floats work or a precision limit of the float datatype you use. Otherwise, you must adhere to the aforementioned probabilities.
  • You may expand the board as much as you like, as long as 1) the result will be theoretically returned at some point in time and 2) the whole expected result is shown.
    • Note: If your language has a board datatype which natively supports unbounded boards, you can use that instead of manually expanding the resulting board, as long as the correct result is returned sometime. You may also use third-party modules which provide such a datatype, or even implement your own, just as long as there is an implementation available online!
| |
\$\endgroup\$
  • \$\begingroup\$ I expect Stencil to win on this one. \$\endgroup\$ – Adám Jan 29 '18 at 17:30
  • \$\begingroup\$ @Adám Sure, that could very well be the case, but what is the problem exactly? Of course some types of challenges are better answered by languages made especially for them, however should we stop posting challenges altogether? ;) \$\endgroup\$ – Erik the Outgolfer Jan 29 '18 at 17:35
  • \$\begingroup\$ It wasn't intended as a criticism. \$\endgroup\$ – Adám Jan 29 '18 at 17:42
  • \$\begingroup\$ Have you tried making a reference implementation? The rules tend to cause extinction. I think changing the chances to 2/3, 3/5, 4/5 works better. \$\endgroup\$ – Adám Jan 29 '18 at 17:47
  • \$\begingroup\$ @Adám I may change the ratios, yeah. I haven't yet gotten around to making a reference implementation. \$\endgroup\$ – Erik the Outgolfer Jan 29 '18 at 17:48
  • \$\begingroup\$ Here you go. N is in the Command-line option. The ratio settings should be obvious. \$\endgroup\$ – Adám Jan 29 '18 at 18:03
  • \$\begingroup\$ @Adám Uh, I was planning to make it myself, but thanks! EDIT: Hm, looks like the implementation is a little bit wrong...maybe this fixes it? \$\endgroup\$ – Erik the Outgolfer Jan 29 '18 at 18:50
1
\$\begingroup\$

Square Number Chains

Background

Given a positive integer n >= 25, it is conjectured that there exists a permutation of the positive integers which are less than or equal to n in which every adjacent pair of numbers adds up to a square number. There are also several numbers less than 25 that this is also true for - 15, 16, 17, and 23.

The Challenge

Write a program or function which accepts a positive integer, n, and returns all positive integers less than or equal to n, ordered such that each adjacent pair adds up to a square number. If there are multiple valid orderings, only one needs to be returned, but your program must be deterministic - that is, for a particular input, your answer should return the same output every time.

You can assume that the input will always have at least one solution, so you don't have to deal with inputs 1-14, 18-22, or 24. If you prefer, you can require that input to your submission will always be greater than 24 - if so, please specify in your submission.

Output may be in the form of a list, or written to STDOUT, so long as there is a consistent and identifiable seperator between them - for example, a space, newline, comma, tab, etc are all fine.

You can validate your program's output by using this TIO link. It supports input as a string with any consistent separator, and will tell you what criteria (if any) your list is failing on.

Inspiration

The Square-Sum Problem - Numberphile

Test cases

Input    Example output
15       9,7,2,14,11,5,4,12,13,3,6,10,15,1,8
23       18,7,9,16,20,5,11,14,2,23,13,12,4,21,15,10,6,19,17,8,1,3,22

Winning Criteria

This is , so the shortest answer in bytes will be the winner! Good luck and happy golfing!


TODO

-More test cases

Feedback requested:

The Python program I've thrown together to provide solution verification is probably a bit shonky, I'm not that strong a Python programmer. If anyone has any comment/criticisms feel free to let me know, or improve it yourself!

As has been pointed out that this challenge is similar to a few others which ask for a Hamiltonian cycle. In my opinion this is suitably different, as this is looking for a Hamiltonian path, and the input is far simpler than the other challenges. What do people think?

| |
\$\endgroup\$
  • \$\begingroup\$ Numberphile's conjecture :P \$\endgroup\$ – Mr. Xcoder Jan 11 '18 at 17:17
  • \$\begingroup\$ What's the winning criterion? Since the conjecture talks about integers >= 25, you should add testcases for those and probably restrict input to that range as well. \$\endgroup\$ – ბიმო Jan 15 '18 at 22:02
  • \$\begingroup\$ @BMO Oops, you're right, I'd forgotten to mention that this is intended to be code golf, good spot. I've mentioned in the 2nd paragraph of The Challenge that you can expect the input to result in at least one solution, does that cover your concern about restricting the input range? \$\endgroup\$ – Sok Jan 16 '18 at 8:58
  • 2
    \$\begingroup\$ Dupewatch: this is Hamiltonian path, which is rather similar to Hamiltonian cycle, which has been done at least three times: codegolf.stackexchange.com/q/11310/194 , codegolf.stackexchange.com/q/31898/194 , codegolf.stackexchange.com/q/67611/194 \$\endgroup\$ – Peter Taylor Jan 16 '18 at 13:01
  • \$\begingroup\$ @Sok: Yeah I read that I just thought that it'll make the challenge more consistent. \$\endgroup\$ – ბიმო Jan 16 '18 at 23:50
1
\$\begingroup\$

First sandbox, so sorry if I'm doing this wrong.

The game involves an API which I haven't yet implemented or deployed, but I'd love to have it done in the next couple of days...

API Easter egg hunt!

There's an API at http://easter_egg_hunt.andrewfaraday.com (I'm aware this is pointing to one of my other sites until I fix it.) which will provide a special Easter egg hunt, just for you...

The API:

These examples are in a 5x5 garden, for illustration only. The API will actually operate on a 100x100 garden (from indexes 1 to 100)

/new_game

Internally, the API produces a garden, and hides an egg in it.

In this example the egg is at 4, 4

+----------+
|          |
|          |
|          |
|          |
|   E      |
|          |
|          |
|          |
|          |
|          |
+----------+

Call

/new_game

Returns

{game_id: 'abcde'}

/guess/:game_id/:x/:y

The API looks in the garden and tells you how close you are.

If you guess 2 across and 8 down, the garden looks like this

+----------+
|          |
|          |
|          |
|          |
|   E      |
|          |
|          |
| g        |
|          |
|          |
+----------+

Call

/guess/abcde/2/8

Returns

{x: '>', y: '<'}

This means: * Your x is too low (the egg position is higher) * Your y is too high (The egg position is lower)

Correct call:

/guess/abcde/4/4

Returns

{x: '=', y: '='}

The Rules

Write a program to find the Easter egg with an API.

  • Use any language.
  • Try to write concise, but readable code.
  • Your program MUST call '/new_game' every time, and use the game_id returned in all 'guess' calls. No peeking at the garden!

This is not code golf, I'll decide on the best answer by number of votes.

| |
\$\endgroup\$
  • \$\begingroup\$ @Adám That's correct. As I noted at the top, I haven't implemented the API yet. I'm sandboxing while I work on the API. \$\endgroup\$ – AJFaraday Mar 28 '18 at 16:59
  • \$\begingroup\$ Oh, I read the text wrongly as which I haven't implemented or deployed. Sorry \$\endgroup\$ – Adám Mar 28 '18 at 17:00
  • 1
    \$\begingroup\$ Looks like an interesting challenge, but a pity that languages without internet support cannot participate. Maybe you could widen the participation by letting submissions query to stdout and receive status from stdin. \$\endgroup\$ – Adám Mar 28 '18 at 17:02
  • \$\begingroup\$ Complement challenge: Implement the "server", receiving requests on stdin and sending status on stdout. \$\endgroup\$ – Adám Mar 28 '18 at 17:03
  • \$\begingroup\$ @Adám How would that help? Without writing a companion program to set up the garden locally? \$\endgroup\$ – AJFaraday Mar 28 '18 at 17:03
  • \$\begingroup\$ @Adám Maybe next Easter? ;) \$\endgroup\$ – AJFaraday Mar 28 '18 at 17:03
  • \$\begingroup\$ Well, you could supply a companion program in a cross-platform language. Or you could combine the two challenges and have submissions need to supply two programs; a client and a server. \$\endgroup\$ – Adám Mar 28 '18 at 17:05
  • \$\begingroup\$ @Adám Isn't inter-application communication a bit of a lengthy process for a code challenge? I'd like to keep it as light and casual as I can. Or at least implement the server part as a different question. \$\endgroup\$ – AJFaraday Mar 28 '18 at 17:06
  • \$\begingroup\$ One wouldn't actually need to implement the comms, each program could be tested with the "user" being the other party. \$\endgroup\$ – Adám Mar 28 '18 at 17:08
  • \$\begingroup\$ @Adám I don't see a downside to requiring the internet support. Not every challenge has to be accessible to every language. \$\endgroup\$ – AdmBorkBork Mar 29 '18 at 18:52
1
\$\begingroup\$

Hyperprogramming: X×Y, X^Y, X^^Y all in two

, just like the original.

Heavily inspired by Hyperprogramming: N+N, N×N, N^N all in one.

Your task is to write two programs so that they compute different hyperoperations when they are placed in relation to each other in the form of the mathematical notation for that hyperoperation.

Full rules:

Write two rectangular programs of the same size — call them "program A" and "program B" — that each take a single positive integer as input and output that integer. In this case, "rectangular" means that every line is the same length, and that there is no trailing newline. Thus, your two programs will each be composed of M lines of N bytes each.

The catch is that when the two programs are placed next to each other in various positions, they will act as a single program that takes two positive integers, X and Y, as input and outputs either X×Y, X^Y, or X^^Y (tetration), depending on the position. Moreover, when the locations of the two programs are reversed, the resulting program will print Y×X, Y^X, or Y^^X — e.g., with X and Y reversed.

The precise location of the two programs with respect to each other is determined by the notation for that particular operation. For instance, if your program A reads

*this* is
program A

and your program B reads

*this* is
program B

your program to output X×Y must contain both program's source codes placed horizontally adjacent without any filler inserted, like so:

*this* is*this* is
program Aprogram B

Because multiplication is commutative, both [AB] and [BA] must function identically.

Your programs to output X^Y and Y^X must contain the code of programs A and B in the locations [ᴀᴮ] and [ʙᴬ], with spaces padding the "exponent" program to the correct horizontal position and optional trailing spaces after each line of the "base" program to pad the layout into a rectangle — no partial padding allowed, it's all or nothing. Padding must be consistent for both X^Y and Y^X (as well as X^^Y and Y^^X later). Illustrated without trailing spaces:

         *this* is
         program B
*this* is
program A

and

         *this* is
         program A
*this* is
program B

Finally, your programs to output X^^Y and Y^^X must contain the code of programs A and B in the locations [ᴮᴀ] and [ᴬʙ], with spaces padding the "base" program, and trailing spaces after each line of the "superexponent" program to pad the layout into a rectangle if and only if your X^Y and Y^X programs included trailing spaces as padding. Illustrated without trailing spaces:

*this* is
program B
         *this* is
         program A

and

*this* is
program A
         *this* is
         program B

You do not have to support arbitrarily large integers, but your answer should work for a reasonable range of X and Y — that is, it should probably at the very least support all combinations of X and Y up to 3 except maybe 3^^3 = 7625597484987.

Source code reading is allowed, as it would be very difficult to otherwise distinguish X^Y and X^^Y in many languages.

As this is , fewest bytes wins.

Note: your score is the total byte count of a single one of your original two programs, not any of the hyperoperation-computing ones — for example, if your programs A and B are each 5×5, your score will be 5×5 + 4 newlines = 29. Since both programs A and B will have identical byte counts, it doesn't matter which one you pick.

Is there anything unclear about this? If so, how could I fix it?

| |
\$\endgroup\$
  • \$\begingroup\$ You may want how exacly do you define "newline". See this. \$\endgroup\$ – user202729 Apr 2 '18 at 15:20
1
\$\begingroup\$

Sandbox Notes

  • Which tags should go?
  • Is this uncomputable?
  • Should I add more test cases?

Solve logical statements about arithmetic

Ok, some of these need to go.

Your task is to determine the truth or falsehood of boolean statements about integer expressions.

Integer Expressions:

  • 1 is an integer expression.
  • If a is an integer expression, then (-a) is an integer expression representing its negative.
  • If a and b are integer expressions, then (a+b) and (a*b) are integer expressions representing their sum and product, respectively.
  • A string of lowercase Latin letters is an integer expression if it is in scope. A value in scope in an integer or boolean expression is always in scope in all of its subexpressions.

Boolean Expressions:

  • If a and b are integer expressions, then (a>b) is a boolean expression representing whether a is greater than b.
  • If a and b are boolean expressions, then (a&b) is a boolean expression representing whether they are both true.
  • If a is a boolean expression, then (!a) is a boolean expression testing whether a is false.
  • If v is some string of lowercase letters, and e would be a boolean expression if v was in scope, then (v^e) is a boolean expression that represents whether e is true for any integer value of v.

Task

You will be given a boolean expression in any reasonable format (such as a string or a parse tree). You should output one of two distinct outputs depending on whether this boolean expression can be shown to be true or false.

Test Cases

(x^(!(y^(x>y)))) => True

Read: for all x, it is not the case that any y is less than x.
In other words, there is no number greater than all other numbers.

(!(x^(!(y^((y*y)>x))))) => True

Read: there is a number x which is less than the square of any y.
In other words: there is a number smaller than all squares (any negative number).

(x^(x>5)) => False

Read: all numbers are greater than 5.

(!(x^(!(x>x)))) => False

Read: it is not the case that all numbers are not greater than themselves.
In other words: there is a number greater than itself.

(y^(x^(!((!(y>(2*x)))&(!((2*x)>y)))))) => False

Read: for every two integers x and y, y is neither greater than nor less than 2x.
In other words: there is no number divisible by 2.

(x^((x*x)>x)) => False

Read: all numbers are less than their squares.

(x^(!(x>(x*x)))) => True

Read: there is no integer greater than its square.

| |
\$\endgroup\$
  • \$\begingroup\$ why not have - as the inverter for integers? \$\endgroup\$ – Destructible Lemon Apr 3 '18 at 3:46
  • \$\begingroup\$ @DestructibleLemon That was originally because I planned to add subtraction, but then decided to keep it minimal. I'm going to change that. Thanks for catching it! \$\endgroup\$ – Esolanging Fruit Apr 3 '18 at 3:51
  • \$\begingroup\$ What about !y^(x^!(x>y&x^(a^(b^(x<a*b+1&x>a*b+-1))))&(a^(b^(x+2<a*b+1&x+2>a*b+-1))))))? (Hopefully I got that right.) Read as "for all y there exists x greater than y, such that x is prime and x+2 is prime." \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:23
  • 1
    \$\begingroup\$ In short, yes, it is uncomputable I'm afraid. There's a lot of potential for interesting challenges based on this idea though! One way would be to specify a set of axioms and have it determine whether the statement is provable from those axioms, allowing the possibility that it fails to halt if it isn't. That might be quite complicated for a code-golf challenge though. \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:23
  • \$\begingroup\$ @Nathaniel I somehow failed to realize that you can do prime checking facepalm \$\endgroup\$ – Esolanging Fruit Apr 3 '18 at 4:30
  • \$\begingroup\$ @Nathaniel Do you think it's uncomputable if you remove logical negation? \$\endgroup\$ – Esolanging Fruit Apr 3 '18 at 4:31
  • \$\begingroup\$ Do you mean logical negation (!) or integer negation (-)? (Either way it's not obvious whether it stays uncomputable, I'll have to think about it.) \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:32
  • \$\begingroup\$ @Nathaniel Logical. \$\endgroup\$ – Esolanging Fruit Apr 3 '18 at 4:32
  • \$\begingroup\$ @EsolangingFruit I thought about it for a while and it still wasn't obvious, so I posted a question here \$\endgroup\$ – Nathaniel Apr 3 '18 at 4:49
  • \$\begingroup\$ @Nathaniel The question you posted isn't exactly the same; my axioms are slightly restricted. There are only integers (and therefore there is no division), and without negation there's no way to simulate logical OR or a "there exists" qualifier. If you allow the "there exists" qualifier your Twin Prime example should be fairly easy to rewrite. \$\endgroup\$ – Esolanging Fruit Apr 3 '18 at 4:58
  • \$\begingroup\$ Ah, you're right, I'd for some reason transposed existential (there exists) and universal (for all) quantifiers in my question --- and your point about and vs or is relevant too. I'll reformulate it and repost. \$\endgroup\$ – Nathaniel Apr 3 '18 at 5:11
  • \$\begingroup\$ I've fixed the math.SE question and undeleted it. \$\endgroup\$ – Nathaniel Apr 3 '18 at 5:15
  • \$\begingroup\$ Exactly same model \$\endgroup\$ – l4m2 Apr 3 '18 at 5:28
  • \$\begingroup\$ @EsolangingFruit the math.SE question got an answer that looks correct - even without logical negation it's still undecidable, because it contains a known undecidable problem about whether a polynomial has integer roots. \$\endgroup\$ – Nathaniel Apr 3 '18 at 12:28
  • \$\begingroup\$ Info: l4m2 attempted to make this computable by using program halt status the output (which is in turn uncomputable) in a separate sandbox post. \$\endgroup\$ – user202729 May 9 '18 at 11:46
1
\$\begingroup\$

Antigerrymandering

From this question:

The United States has a unique love of gerrymandering––the deliberate manipulation of an electoral district to predict certain voting results. Just recently there was a gerrymandering case brought before the Supreme Court. Gerrymandering, especially when related to race, is ruled illegal and results in the requirement to redraw the district lines.

Gerrymandering has recently been getting even more attention in the news due to this year's congressional elections. Wouldn't it be nice if we could all decide on a simple, nonpartisan way to determine congressional districts?

Your task is to fix settle this discussion once and for all with a determinate program to partition a map into districts.

What you gotta do

Write a program or function that takes a positive integer n and a map (described below) and partitions the map into n contiguous districts of equal population (as nearly as possible) while minimizing the total length of the districts' borders.

The map

The map is a two-dimensional, rectangular matrix of one or more integers, each integer representing the population of its cell. This can be in any convenient format—an array of arrays, a stream of numbers, or even a JPEG, if desired! You are allowed to take the dimensions of the map as additional inputs.

The borders

Each cell in the map is to be treated as a square of side length 1. Total border length is the sum of the lengths of all edges of cells that are also the edge of a district. Note that this will necessarily include the entire perimeter of the map.

The partition

The n districts must have the lowest possible maximum difference in population from total population / n. In the case of a tie, they must have the lowest possible total border length, ensuring compact districts.

Take the following map:

1 5 7 8
7 4 2 5
8 5 3 5

It has total population 60. To divide it into two districts, each must have population 30. Additionally, each district must be orthogonally contiguous. Both of the following accomplish just that:

1│5 7 8
 └───┐
7 4 2|5
     │
8 5 3│5


1 5│7 8
   │
7 4│2 5
   │
8 5│3 5

Of these two partitions, the upper has total border length 14 (perimeter) + 5 (border) = 19, while the lower has length 17. Of these two options (and the other one I can see at the moment, the vertical line down the middle is to be chosen, since its border length is the lowest.

Now consider:

2 1 2

This again has two possible partitions into two districts, but these are tied in border length. Your program or function can return either partition, but it must return the same one each time.

Output

Lots of options. A string using one non-numeric character for border and another for no border. An array of numbers, with a surjection to the sixteen possible states of a cell's edges. A JPEG, with borders shaded. A pirate's map: "3 steps south. 2 steps east..." Really, anything that can be mapped to a partition. The output format must be consistent.

This is , so the shortest solution (in bytes) in each language wins!


Sandboxy stuff

Any clarification needed?

I'm making some test cases (based on real states' population distributions!); these'll be added soon.

Anything else worth mentioning?

Thanks!

| |
\$\endgroup\$
  • \$\begingroup\$ While flexible output formats are commendable, I personally wouldn't want to check the validity of a program with output formats as broad as "anything that can be mapped to a partition". Now, checking validity of every answer isn't my job or anything, but I would want to have the option not be prohibitive. \$\endgroup\$ – Kamil Drakari Apr 4 '18 at 19:39
  • \$\begingroup\$ thematically related, although going in the opposite direction \$\endgroup\$ – Giuseppe Apr 4 '18 at 19:59
  • \$\begingroup\$ @KamilDrakari I'll think further on it. Thanks. \$\endgroup\$ – Khuldraeseth na'Barya Apr 4 '18 at 20:06
  • \$\begingroup\$ @Giuseppe Yep. Meant to link in the question, but wrong link :) \$\endgroup\$ – Khuldraeseth na'Barya Apr 4 '18 at 20:07
  • \$\begingroup\$ Will the "real" test cases be small? I ask because a golfed answer to the question as it stands is likely to be geologically slow. \$\endgroup\$ – Peter Taylor Apr 6 '18 at 10:00
1
\$\begingroup\$

Find the Intersection

Challenge

Given some planes in an n-dimensional space, return the intersection of these planes with the highest degree, if it exists.

Details

You will be given two integers, n and k, such that 0 < k ≤ n and 1 < n. You will also be given (n-k) hyperplanes within the space Rn. (A hyperplane in the space Rn has (n-1) dimensions.) Your task is to find the intersection between them that has the highest number of dimensions, if it exists. This intersection will have at least k dimensions; it may have more than k dimensions if the inputs are not independent.

For example, if we are working in the 3-dimensional space (R3), you would be given planes with 2 dimensions. If you are given 3 distinct planes, you would at best be able to find a single point where they all intersect (0 dimensions). If you are given 2 distinct planes, you could find a line where they intersect (1 dimension). Et cetera.

Input format

You may choose any standard format to represent hyperplanes in Rn. Here are two formats that I suggest:

  1. vn = c1v1 + c2v2 + ... + cn-1vn-1 + cn, where v represents a variable and c represents a scalar constant.

  2. c1v1 + c2v2 + ... + cnvn + cn+1=0.

For example, consider the plane z=2x-3y in R3. In format 1, I would write this as v3=2v1-3v2+0, so my program would take in the tuple of scalar constants (2, -3, 0). In format 2, I would rewrite this as 2x-3y-z+0=0, and similarly take the tuple (2, -3, -1, 0). You can choose one of these two formats or another standard format, so long as you provide details in your answer.

You may take in n and k explicitly if you wish, though you should be able to determine both from the list of planes (k is the number of planes, n is one more than the number of dimensions in a plane).

Output format

You should output a single plane in the same format as your input. If no intersecting plane exists, you should return something recognizably distinct from other valid outputs of your program (such as an empty tuple, false, a thrown exception, etc.).

Test Cases

These use suggested input format 1, with n and k provided implicitly.

[(c1, c2, ..., cn), (...), ...] => (c1, c2, ...)

In R3, the intersection of z=-3x-2y, z=5+2x+3y, and z=-x-y-1 is the point (2, -3, 0)

[(2, 3, 5), (-3, -2, 0), (-1, -1, -1)] => (2, -3, 0) // This doesn't work

In R3, the intersection of z=4x+y and z=x+2y+1 is the line y=3x-1

[(4, 1, 0), (1, 2, 1)] => (3, -1)

Scoring criteria

This is , so the shortest answer in each language wins.


Meta

Can you follow the goal of the challenge and the details I've provided? I've tried to be as clear as possible, but I think I may have been too verbose.

I think my output format needs to change - there's no way to represent a point in Rn the way I've phrased it...any suggestions?

More test cases coming soon.

| |
\$\endgroup\$
  • \$\begingroup\$ The specified input formats force the hyperplane to pass through the origin, but nothing else in the question indicates that restriction. \$\endgroup\$ – Peter Taylor Mar 29 '18 at 13:56
  • \$\begingroup\$ Good point. I will fix that, thank you \$\endgroup\$ – musicman523 Mar 29 '18 at 16:25
  • \$\begingroup\$ "this can be higher if some of the inputs are equal" should really be "this can be higher if some of the inputs are not independent": three planes can pass through a line without any of them being equal. Other than that, I think you just need the test cases. \$\endgroup\$ – Peter Taylor Apr 3 '18 at 13:48
  • \$\begingroup\$ Thanks, this is the feedback I was looking for. I knew there were some holes in my math :) \$\endgroup\$ – musicman523 Apr 4 '18 at 14:09
1
\$\begingroup\$

Get Rid of GoTo's

My (pseudo) code is full of goto's! What a mess... Let's change it into a more iterative code.

SPECIFICATION

Each input consists of:

<HEADER> { 
  0: <code> 
  1: <code> (optional) 
  2: <code> (optional) 
  ... 
  99: <code> (optional) 
}

where:

<HEADER>: It is the method signature, but it can be anything. Just repeat it in the output.

<code>: It is the main code that contains the unwanted goto's and need to be refactored. It is always numbered, starting at 0 and increasing sequentially. code can be one of:

  • if [condition] goto [number] [trailing]: this is where the goto's are. The if clause contains any text as a condition, that should be repeated in the output. The number should be between 0 and 99, and should point to a valid line in the input. The trailing could be a semicolon, a text comment or even nothing at all, but it will not appear in the output.
  • return: the return clause is special because it ends the method execution. In the input code, a return could be followed by others lines reachable by a goto. But in the output code, a return is never followed by a code line. The return can be followed by a semicolon or nothing at all.
  • anything: anything else is just code clauses that should be repeated somewhere in the output code.

EXAMPLES

BEFORE:

method1() {
    0: printMessage("This is the firstMethod");
    1: if (inputString(0)) goto 3;
    2: return;
    3: setVar(10);
    4: printMessage("Var is set to 10");
}

AFTER:

method1() {
    0: printMessage("This is the firstMethod");
    1: if (inputString(0)) {
    2:  setVar(10);
    3:  printMessage("Var is set to 10");
    4: } else {
    5:  return;
    6: }
}

This is the simplest example. The goto is changed into an if/else structure. The 'return' clause always ends a block (i.e., the code does not continue after it).

BEFORE:

public method2() {
    0: addFlag(char, 1);
    1: play(22, 3468, 4433);
    2: int rndNum = random(3)
    3: if(rndNum == 1) goto 6
    4: if(rndNum == 2) goto 8
    5: if(rndNum == 3) goto 10
    6: addItem(36, 54, 0, 0);
    7: return;
    8: addItem(37, 54, 0, 0);
    9: return;
    10: addItem(38, 54, 0, 0);
    11: return;
}

AFTER:

public method2() {
    0: addFlag(char, 1);
    1: play(22, 3468, 4433);
    2: int rndNum = random(3)
    3: if(rndNum == 1) {
    4:     addItem(36, 54, 0, 0);
    5:     return;
    6: } else {
    7:     if(rndNum == 2) {
    8:         addItem(37, 54, 0, 0);
    9:         return;
    10:    } else {
    11:        if(rndNum == 3) {
    12:            addItem(38, 54, 0, 0);
    13:            return;
    14:        } else {
    15:            addItem(36, 54, 0, 0);
    16:            return;
    17:        }
    18:    }
    19: }
}

This example is trickier. The three gotos end up creating nested if/else clauses. Also, as the transpiler can't know if rndNum(3) returns something from [1-2-3], there is also an ultimate else clause afterwards.

BEFORE:

public method3() {
    0: int curChar = whoMenu("Test", "Super");
    1: if (firstChar(currentChar, 1)) goto 5;
    2: printMessage("The sun is hot.");
    3: if (YesNo(1)) goto 17;
    4: return;
    5: addVar(currentChar, 10);
    6: addVar(currentChar, 20);
    7: addVar(currentChar, 30);
    8: addVar(currentChar, 40);
    9: addVar(currentChar, 50);
    10: addVar(currentChar, 60);
    11: addVar(currentChar, 70);
    12: addVar(currentChar, 80);
    13: addVar(currentChar, 90);
    14: addVar(currentChar, 100);
    15: printMessage("You feel good");
    16: if (YesNo(1)) goto 17;
    17: addFlag(currentChar, 82);
}

AFTER:

public method3() {
    0: int curChar = whoMenu("Test", "Super");
    1: if (firstChar(currentChar, 1)) {
    2:    addVar(currentChar, 10);
    3:    addVar(currentChar, 20);
    4:    addVar(currentChar, 30);
    5:    addVar(currentChar, 40);
    6:    addVar(currentChar, 50);
    7:    addVar(currentChar, 60);
    8:    addVar(currentChar, 70);
    9:    addVar(currentChar, 80);
    10:   addVar(currentChar, 90);
    11:   addVar(currentChar, 100);
    12:   printMessage("You feel good");
    13:   if (YesNo(1)) {
    14:         addFlag(currentChar, 82);
    15:   }
    16: } else {
    17:     printMessage("The sun is hot.");
    18:     if (YesNo(1)) {
    19:         addFlag(currentChar, 82);
    20:     } else {
    21:         return;
    22:     }
    23: }
}

This example is not so hard, but note there are two goto's going to the same line. As this line does not create a loop, it is permitted (see rules below).

BEFORE:

method4() {
    0: printMessage("This is the firstMethod");
    1: if (inputString(0)) goto 4;
    2: printMessage("End is near.");
    3: return;
    4: setVar(10);
    5: if (inputString(1)) goto 2;
    6: printMessage("Var is set to 10");
}

AFTER:

method4() {
    0: printMessage("This is the firstMethod");
    1: if (inputString(0)) {
    2:     setVar(10);
    3:     if (inputString(1)) {
    4:         printMessage("End is near.");
    5:         return;
    6:     } else {
    7:         printMessage("Var is set to 10");
    8:     }
    9: } else {
    10:    printMessage("End is near.");
    11:    return;
    12: }
}

This example is also tricky, because it contains a goto to a previous line. This does not create a loop, but it also creates a block that is repeated twice in the code.

CONSIDERATIONS:

1) Goto's are always associated with an 'if' clause. Replace the goto with a start block '{' clause.

2) Goto's always create an 'if', but not necessarily an 'else'.

3) Some clauses can repeat due to more than one goto's going to the same line (directly or not).

4) There won't be loops. Example of invalid code:

public methodInvalid() {
    0: if(YesNo(1)) goto 2;
    1: printMessage("this code is invalid.");
    2: if(NoYes(1)) goto 0;
    3: printMessage("still invalid.");
}

5) Identation in the output is desirable. Each if/else block must be nested with a tab for each nested level. If you want to replace the tab for 2, 3 or 4 spaces, ok, just state it and make it coherent on your code.

6) As there won't be more goto's, the line numbers are optional in the output code. Just don't put them out of order, if you want to keep them.

7) The first line can be ignored (just repeat it in the output) and the last line is always the close statement ('}'). These lines are never numbered.

8) The input will always contains line numbers, starting with 0 and a colon. The next line will be 1 and a colon, and so on. No more than 99 lines will be present.

9) There is also at least one space (or tab or opening parenthesis) after the if statement, one space before the goto statement and one space before the number after it. So "1:ifagoto2" is invalid, but "1:if a goto 2" is valid and also valid is "1: if(a) goto 2". Spaces (or tabs) are optional before the line numbers and between the semicolon and the start of the code.

10) You only need to worry with (a) 'goto's; (b) line numbers; (c) the 'return' clause; and (d) the end of the code (last line). Everything else is gibberish, you don't need to interpret the code. See a valid input below:

BEFORE:

fun with code {
    0: gibberish
    1: if a goto 3
    2: gibberish
    3: gibberish
    4: gibberish
}

AFTER:

fun with code {
    0: gibberish
    1: if a {
    2:  gibberish
    3:  gibberish
    4: } else {
    5:  gibberish
    6:  gibberish
    7:  gibberish
    8: }
}

Standard loopholes apply, shortest answer in bytes wins!

| |
\$\endgroup\$
  • \$\begingroup\$ Will line number always start with 0 and increase by 1? Is there any un-conditional goto? Will there be any dead code in the input? \$\endgroup\$ – tsh Apr 8 '18 at 1:32
  • \$\begingroup\$ @tsh Yes, the number always start with 0 and increase by 1. No, goto's are always preceded by if's. Dead code in the input? I think so, there is no restrictions against that. \$\endgroup\$ – Chaotic Apr 8 '18 at 23:54
  • \$\begingroup\$ Suggested title: Code golf considered harmful. \$\endgroup\$ – Nathaniel Apr 9 '18 at 4:13
  • \$\begingroup\$ Is if(a)goto 2 allowed? \$\endgroup\$ – l4m2 Apr 9 '18 at 12:57
  • \$\begingroup\$ @l4m2 No, because "There is at least ... one space before the goto statement" \$\endgroup\$ – Chaotic Apr 9 '18 at 15:08
1
\$\begingroup\$

Scoring a Game of Composite Boards

The Game

Given a board size n which must be a composite number, the game is played on m boards in parallel which correspond to the m factors of n, excluding 1 and n itself.

E.g. if n = 12, we get the following 4 boards, where the same character represents the same field:

01     012     0123     012345
23     345     4567     6789AB
45     678     89AB
67     9AB
89
AB

Two players, Zero and One, take turns in writing a 0 or 1 respectively on an empty field, which makes that number appear on all boards at the corresponding field.

On each board their goal is to get more rows or columns filled with just their number than their opponent, resulting in the board being either a win for Zero, a win for One or a draw if both players fill the same number of rows or columns.

The game is won by the player who wins the majority of boards, or results in a draw if both players win the same number of boards.

Example

Let's say we have the game 010111010100 of size 12, which corresponds to the following boards:

01
01
11 <- row for player One
01
01
00 <- row for player Zero
no columns for either player -> draw

010
111 <- row for One
010
100
-> One wins this board

0101
1101
0100
 ^^
 one column for each player -> draw

010111
010100
^^^^
two columns for each player -> draw

As player One wins one board and player Zero wins none, player One wins the game.

The Task

Given a completed game as input, output which player won or whether the game was a draw. This is , so the smallest answer in bytes in each language wins.

Input

A one-dimensional array/list/string of two distinct values representing the fields of the boards when read left-to-right and top-to-bottom. You can assume that the input describes a valid game, that is the length will always be a composite number and the two values appear either the same number of times for even board lengths or with a difference of one for odd board lengths.

Output

Three distinct constant values which correspond to player Zero wins, player One wins or draw.

Test Cases

Draw: (All games of size 2*p where p is prime necessarily result in a draw)

0110
101010
11010010
010101010
11001111000100

Zero wins:

110110000
001001110101
1000110101011001

One wins:

111100001
010111010100
1100111100010010
0111010001001101
| |
\$\endgroup\$
1
\$\begingroup\$

Curve Matching

Given two lists a, b of the same length n find a third list x of indices such that a(i) = b(x(i)) for all indices i and x(i) <= x(i+1) for all applicable indices i and x(1) = 1 and x(n) = n.

Details

  • The list x is not necessarily unique (for instance when b has a run of two or more equal entries).
  • In the challenge description we use 1-based indices, but you can also use 0-based indices.
  • You can assume that a and b contain integers, floating point numbers, characters or any other types that have a natural order and have at least 256 distinct values.

  • You can assume that such an x exists. (You can for instance assume that a=[1,2,3], b=[1,2,1] are never passed as an input.)

Examples

a = b = [1,2,3]
x = [1,2,3]

a = [1,3,3], b = [1,1,3]
x = [1,3,3]

a = [1,1,2,3,4,4], b = [1,2,2,3,3,4]
x = [1,1,2,4,6,6] or [1,1,3,5,6,6] etc

a = [1,1,2,3,2,1,1], b = [1,2,1,2,3,2,1]
x = [1,3,4,5,6,7,7]

This challenge was inspired by this question on math.SE.

| |
\$\endgroup\$
1
\$\begingroup\$

Unless someone can convince me otherwise I think this is too close to Are the brackets fully matched? to be an interesting new challenge, so I won't submit it.

Well-formed Parentheses Gone Wild

The object is to determine if the "parentheses" in a string are well-formed, in the sense that they are balanced and well-nested.

For example [(ab(c!{})n)] is such a string, while [(ab(c!(d)x){)}] is not (balanced, but not well-nested due to the last closing ) appearing before the closing }).

But wait, there's more

Those examples took advantage of the commonly understood meanings of the pairs (), {}, and []. But any characters could be opening and closing parentheses, and not just the obvious ones.

Input

The input consists of two strings with optional trailing newlines. The characters can be any ASCII printable character (hex 20 to hex 7E).

The first string has an even number of characters with no duplicates. Each successive pair of characters defines a pair of opening and closing parentheses. The second string is the test string.

Output

Truthy or falsy value (with optional trailing whitespace) for whether or not the parentheses in the test string are well-formed (balanced and well-nested). If either the first or second strings are empty, the answer is defined to be truthy.

Some Tests

Format:

String1
String2
Output

Tests:

(){}[]
[(ab(c!{})n)]
truthy

(){}[]
[(ab(c!(d)x){)}]
falsy

()[]<>
[(ab(c!(d)x){)}]
truthy

                      <---- empty parenthesis string
%$w%jS(5gS
truthy

(){}[]
                      <---- empty test string
truthy 

qwertyuiop
q##qCfet^Hy&&r$wuiwgJo7({)}erxp
truthy

@#$%^&
super b$fox$#@%%g ongshow^&
falsy

Scoring and Rules

  • This is . Shortest entry wins.
  • Standard loopholes forbidden and standard rules apply.
| |
\$\endgroup\$
  • \$\begingroup\$ I believe this is a duplicate \$\endgroup\$ – Nathan Merrill Apr 20 '18 at 21:03
  • 1
    \$\begingroup\$ @NathanMerrill this challenge has the input define its own parentheses and require that it's well-formed. That would definitely need different code. \$\endgroup\$ – Nissa Apr 20 '18 at 21:19
  • 2
    \$\begingroup\$ Why not go with 2 separate strings in any convenient format? Can the open and close parentheses be the same, e.g. quotes? \$\endgroup\$ – Nissa Apr 20 '18 at 21:23
  • \$\begingroup\$ @StephenLeppik - two strings in a convenient format would be better. The , and ! are not relevant to the problem. Would it be canonical to say "two strings with optional trailing newlines"? I want to include the space ` ` as a possible character in either string. \$\endgroup\$ – ngm Apr 20 '18 at 22:08
  • \$\begingroup\$ @StephenLeppik Open and close parentheses must be different, as implied by the even number of characters with no duplicates in the first string. \$\endgroup\$ – ngm Apr 20 '18 at 22:16
  • \$\begingroup\$ Is it possible to take a list of length-2 string (for the first input)? \$\endgroup\$ – user202729 Apr 21 '18 at 10:09
  • 1
    \$\begingroup\$ This is a better dupe. The 05AB1E answer and the (20-byte) Pyth answer can be directly ported to this challenge. The Javascript answer... need some join-with-| and regex construction. \$\endgroup\$ – user202729 Apr 21 '18 at 10:13
  • \$\begingroup\$ I'm thinking codegolf.stackexchange.com/questions/77138/… is close enough to make this challenge uninteresting. What's the protocol? Do I delete this or just leave it so nobody else tries the same? \$\endgroup\$ – ngm Apr 21 '18 at 17:21
  • 1
    \$\begingroup\$ You could always spice up the rules to make your challenge unique. \$\endgroup\$ – Asone Tuhid Apr 21 '18 at 19:23
  • \$\begingroup\$ What if there was an order on the different parenthesis so that () has to be closed before [] can be open or something along these lines? So your String1 in the example would define an order. \$\endgroup\$ – JayCe Jun 11 '18 at 3:42
1
\$\begingroup\$

Golf the linux kernel

This file [to do: make the file and provide a link] contains all the code in the Linux kernel, concatenated together into a single file. Your task is to output this exact file.

The code in the file has been stripped of all comments, except for the copyright notice at the top, which is a legal necessity in order to distribute it.

This is a challenge, so your score is the size of your submission in bytes, and the smallest score wins.

If your submission will contain multiple files (for example, code and a separate data file), please take note of the rules on scoring and directory structure for multi-file submissions. Any data that your code uses must be included in your score.

Sandbox note

This is an unusual challenge, in that the specified output consists of a really huge file. (Probably in the hundreds of Mb.) Normally that would mean built-in compression methods would dominate, but the Linux kernel has a lot of structure in it, both due to the grammar of C and due to the strict coding standards. For that reason I would expect customised algorithms to out-perform standard ones, so it should make for an interesting open-ended challenge along the lines of Paint Starry Night or Write Moby Dick.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think you should have to output it; your program is a way of distributing it. IANAL though. \$\endgroup\$ – wizzwizz4 Apr 22 '18 at 15:48
  • \$\begingroup\$ Because the header is very small in comparison with the text, it should not be too much of a problem. \$\endgroup\$ – user202729 Apr 22 '18 at 16:15
  • \$\begingroup\$ @wizzwizz4 IANAL either. I imagined it would only count as distribution if you give it to someone else. But since I'm not sure I've changed it for now. \$\endgroup\$ – Nathaniel Apr 22 '18 at 16:15
  • \$\begingroup\$ @Nathaniel You're giving it to everybody on the internet, so it's distribution. \$\endgroup\$ – wizzwizz4 Apr 22 '18 at 16:15
  • \$\begingroup\$ @wizzwizz4 right, and that's why I'm including the header. But for someone running their own program and verifying the output, they wouldn't be giving it to anyone, hence no need to reproduce the header. But I've changed it for now anyway. \$\endgroup\$ – Nathaniel Apr 22 '18 at 16:17
  • \$\begingroup\$ @Nathaniel That's true. If somebody submitted it, though... (This is just for others reading this; I'm not arguing with you.) \$\endgroup\$ – wizzwizz4 Apr 22 '18 at 16:17
  • \$\begingroup\$ @user202729 it shouldn't be a problem by the numbers, but it would result in a challenge that amounts to "compress this huge amount of code (plus this small amount of English text)", which I thought might be annoying. Not really sure though. \$\endgroup\$ – Nathaniel Apr 22 '18 at 16:19
  • \$\begingroup\$ @wizzwizz4 gah, that opens up a whole can of worms I hadn't thought of - the entries to this competition probably count as works derived from the Linux kernel, and hence have to be distributed under the GPL themselves. That probably spells the end for this challenge idea, unless I use some other large body of code that's public domain or released under a much more permissive license. \$\endgroup\$ – Nathaniel Apr 22 '18 at 16:22
  • \$\begingroup\$ @Nathaniel Oh... Well, erm... I don't think they... Wait, they would... Ask on Open Source. They'll know. \$\endgroup\$ – wizzwizz4 Apr 22 '18 at 16:23
  • \$\begingroup\$ It might be a good idea to change scoring to be more like the Moby Dick and Starry Night challenges, where the scoring is based on "similarity" rather than requiring an exact match. I think that should get around some of the Open source issues since the output wouldn't really contain the kernel or anything runable at all, and imo tends to favor custom implementations over built-in compression due to higher tolerance for lossy approximations. \$\endgroup\$ – Kamil Drakari Apr 22 '18 at 17:03
  • \$\begingroup\$ @KamilDrakari Then there would be empty submissions... no. Also how will it be different from Moby Dick then? \$\endgroup\$ – user202729 Apr 23 '18 at 0:18
  • \$\begingroup\$ @user202729 if I wanted to go in that direction, there is a numerical parameter in the Moby Dick scoring system, which in retrospect was set a bit too high. I could change it to L+E or even 0.5L+E, which would result in a significantly different challenge, and the different regularities in the target text would make a big difference also. But I doubt that would really get around the legal issues, and I prefer the pure-ness of this idea, if I can get it to work. I'll just have to find a project with a different license - I'm sure that exists somewhere. \$\endgroup\$ – Nathaniel Apr 23 '18 at 1:54
  • \$\begingroup\$ Or I could use a completely different similarity measure. I've been thinking about something based on log loss, which would work much better as a similarity metric, at the cost of being more complicated to explain and implement. A follow-up to Moby Dick is in the works at some point, but I'm very aware of the need to make it different enough from the original. \$\endgroup\$ – Nathaniel Apr 23 '18 at 1:58
  • 3
    \$\begingroup\$ I've seen claims similar to "For that reason I would expect customised algorithms to out-perform standard ones" fail to be backed up by answers outperforming standard algorithms enough times that IMO it's not worth posting a kolmogorov-complexity challenge unless you have written a reference answer which outperforms bzip2 and gzip. \$\endgroup\$ – Peter Taylor Apr 25 '18 at 11:35
  • 1
    \$\begingroup\$ @PeterTaylor that's a fair point --- if I find a body of code with a suitable license I will do that, and I won't post if I'm wrong. (I did a similar test for Moby Dick.) \$\endgroup\$ – Nathaniel Apr 25 '18 at 11:40
1
\$\begingroup\$

Sandbox notes

  • Is there anything that is unclear?

Double Language Supersets

For the purposes of this challenge:

  • A language is a partial mapping from programs (strings of bytes) to outputs (streams of bytes). Not every output must be finite or produce any elements before looping indefinitely.
  • A language L is an superset of another language K if, for every program of length n given meaning in K, there is a program of length n given meaning in L which produces the same output. In other words, all programs in K can be translated into L without requiring any more bytes.

(cops' part)

As a cop, you must:

  • Find two languages, and provide (or link to) a specification in the form of a detailed description or an implementation. Be prepared to answer any questions should ambiguities arise.
  • Define a new "solution" language which is a superset of both of the others. This can be in the form of a detailed document, implementation, or a proof that such a language exists.

You should reveal the first two languages, but keep the solution language secret.

The cop whose submission takes the longest to crack is the winner.


(robbers' part)

As a robber, you must:

  • Find an existing cop submission.
  • Define a new language which is a superset of both of the languages provided by the cop. This can be in the form of a detailed description, an implementation, or a proof that such a language exists.

The robber who cracks the most cop submissions is the winner.

| |
\$\endgroup\$
  • \$\begingroup\$ So it's a partial mapping? \$\endgroup\$ – user202729 Apr 22 '18 at 14:00
  • \$\begingroup\$ @user202729 Yes \$\endgroup\$ – Esolanging Fruit Apr 22 '18 at 22:36
  • \$\begingroup\$ I don't think that polyglot makes sense here. \$\endgroup\$ – Nissa Apr 23 '18 at 14:16
  • \$\begingroup\$ I don't think this really makes sense as a c'n'r. Both cops and robbers are trying to do the same thing, which is to prove that every program which is valid in both languages gives the same output in those languages. The robber doesn't have to outwit the cop by beating a score or working within extra constraints which the cop chooses and can try to use to add false clues. The only real asymmetry is that the cop chooses the languages, and the only way to exploit that to make it interesting is to make one of them a homebrew which is "specified" with an obfuscated implementation. \$\endgroup\$ – Peter Taylor Apr 25 '18 at 10:56
1
\$\begingroup\$

Decode my Alphabet Code (Cops)

This is my first C&R challenge, so I thought I'd better post it in the sandbox. This is only the Cops thread and it's still missing some usual C&R rules (such as explaining what should be done once a submission has been cracked).


This is the Cops' thread of a challenge. [Link to the Robbers' thread goes here.]

Your task

As a Cop, you must write either a full program or a function that meets the following requirements.

Input

A non-empty string made of at most 26 distinct characters in a given code page. The input is guaranteed to be valid.

The code page is either UTF-8 or -- at your option and if applicable -- a specific code page used by your language.

Output

A string of the same length and in the same code page where the first encountered character is replaced with A, the second encountered character (distinct from the first one) is replaced with B, and so on.

For instance, the expected output for Hello, World! is ABCCDEFGDHCIJ, where A=H, B=e, C=l, etc.

Code restriction

Your code must be a valid input for itself. In other words, it must consist of at most 26 distinct characters in the chosen code page. (But of course, each distinct character may be used several times.)

Your submission

Your submission must contain:

  • The language used
  • The code page used
  • The size of the code in this code page
  • A brief description explaining the nature of your code (program or function) and the I/O formats it's using, in case it slightly differs from string/string.
  • The output produced by applying the transformation to your code

Example:

# MyLanguage, 32 characters in MyLanguage code page

A function taking an array of characters and returning a string.

ABCADAEFGHIEJKDKLMEBCLNEOPPJLNEO

Robbers' task

Robbers must crack your submission by finding a working program that produces exactly the same output once transformed. (Finding a shorter program is not a valid crack.)

Rules

If your answer remains uncracked for a week, you can mark it as Safe and unveil the original code.

The winner is the shortest uncracked answer. In the case of a tie, the oldest answer wins.


Sandbox questions

  • Is it a dupe or too close to an existing challenge?
  • In the original version, the encoding was forced to UTF-8. I'm still not sure which option is the best, so I'm interested in any feedback about that.

  • All other comments and suggestions are much welcomed!

| |
\$\endgroup\$
  • \$\begingroup\$ Do spaces count too ? \$\endgroup\$ – Muhammad Salman Apr 24 '18 at 14:16
  • \$\begingroup\$ @MuhammadSalman Yes, all distinct characters are taken into account. (The space becomes F in my Hello, World! example.) \$\endgroup\$ – Arnauld Apr 24 '18 at 14:18
  • \$\begingroup\$ I suggest only using bytes. Most languages I know of have SBCS anyway, otherwise the translation from UTF8 to bytes are straightforward enough. \$\endgroup\$ – user202729 Apr 24 '18 at 14:20
  • \$\begingroup\$ To be clear, this is not code-golf, correct? \$\endgroup\$ – user202729 Apr 24 '18 at 14:24
  • \$\begingroup\$ @user202729 Using only bytes is indeed another possibility. But it may make the submissions quite harder to check. For instance, if you pass the posted UTF-8 representation of a Jelly program to this same Jelly program which is expecting it in its own code page instead, it's likely to fail. \$\endgroup\$ – Arnauld Apr 24 '18 at 14:34
  • \$\begingroup\$ @user202729 I need to add that the shortest uncracked answer wins. So, I suppose it should be tagged as code-golf as well? (Although the primary winning criterion is to remain uncracked.) \$\endgroup\$ – Arnauld Apr 24 '18 at 14:35
  • \$\begingroup\$ If a language only uses less than 26 characters, can we only support up to that many letters of the alphabet? \$\endgroup\$ – Jo King Apr 25 '18 at 10:30
  • 2
    \$\begingroup\$ @JoKing No, the program must support all inputs. (But of course it's fine if the code itself is only using a couple of distinct letters.) \$\endgroup\$ – Arnauld Apr 25 '18 at 10:37
1
\$\begingroup\$

Integers as "polynomials"

Suppose we use successive digits of an non-negative integer for coefficient, base and power respectively and construct a "polynomial". For a 4-digit number we'll have:

abcd -> a*b^c + b*c^d + c*d^a + d*a^c.

Each digit must go through the three roles exactly once. For the last two members we wrap around the right edge and use the first/second digit again.

For example 1234 will represent the following "polynomial":

1*2^3 + 2*3^4 + 3*4^1 + 4*1^2 -> 1*8 + 2*81 + 3*4 +4*1 -> 186

We started with an integer and ended with an integer. That gives me the idea that we can feed the result into the procedure again and keep calculating. As it seems the numbers will sooner or later start repeating, leading to an endless loop. For example:

4 -> 1024 -> 12 -> 4 -> ...

I'm interested in how many cycles are needed until we come to a number that has already been calulated.

The Task:

Start with a non-negative integer and calculate my "polynomial" from it. Keep calculating using the result as input until you reach a number that has already been calculated.

Your answer must be theoretically correct if your language's integer types had infinite width, but you may use any integer type with at least 8 bits

Input:

You can take the input as:

  • A non-negative integer
  • A list of digits
  • A string

Output:

A single integer - the number of cycles until a known number is reached.

Winning criteria:

This is , so shortest code in bytes in each language wins. Explanations of the code are welcome!

Test cases:

 0:  1
 1:  1
 2: 34
 3:  5
 4:  3
 5:  3
 6: 29
 7: 48
 8: 33
 9: 20
10:  1
11: 35
12:  3
13: 30
14: 34
15:  2
16:  3
17: 35
18:  4
19:  5
20:  1
21:  3
22:  4
23: 79
24: 78
25: 36
26: 34
27: 15
28: 41
29: 57
30:  1
31: 30
32: 79
33:  3
34: 10
35: 45
36: 32
37:  9
38: 64
39: 10
40:  1
41: 34
42: 78
43: 10
44: 30
45: 16
46: 39
47: 13
48: 96
49:  7
50:  1
51:  2
52: 36
53: 45
54: 16
55: 11
56: 40
57:  4
58: 12
59: 17
60:  1
61:  3
62: 34
63: 32
64: 39
65: 40
66: 30
67:  4
68:  6
69: 77
70:  1
71: 35
72: 15
73:  9
74: 13
75:  4
76:  4
77:  9
78: 38
79:  6
80:  1
81:  4
82: 41
83: 64
84: 96
85: 12
86:  6
87: 38
88: 97
89: 13
90:  1
91:  5
92: 57
93: 10
94:  7
95: 17
96: 77
97:  6
98: 13
99: 69

| |
\$\endgroup\$
  • \$\begingroup\$ "Not surprisingly the numbers will sooner or later start repeating, leading to an endless loop" Do you have a proof of this? It seems plausible but not obvious that no chain escapes to infinity. \$\endgroup\$ – Peter Taylor Apr 30 '18 at 14:59
  • \$\begingroup\$ @Peter Taylor - No, I don't have any proof. Maybe I need to change the description? \$\endgroup\$ – Galen Ivanov Apr 30 '18 at 15:18
  • 1
    \$\begingroup\$ I've found a proof: 12 x 9<sup>10</sup> = 4.1841412812 x 10<sup>10</sup>, so any number with 12 or more digits maps to a number with fewer digits. There is one thing which I think it's probably worth adding, and that's a statement about overflow. Options include "Your answer must be correct if intermediate values don't exceed N bits, but may be incorrect if they do exceed that"; "Your answer must be theoretically correct if your language's integer types had infinite width, but you may use any integer type with at least 8 bits". \$\endgroup\$ – Peter Taylor Apr 30 '18 at 15:41
  • \$\begingroup\$ @ Peter Taylor Thank you for your help! You are completely right abiut the overflow - I have used J's extended precision to make the test cases. I'm going to update the description. \$\endgroup\$ – Galen Ivanov May 1 '18 at 8:35
1
\$\begingroup\$

Relational Division

Given a database of colored marbles in bins, find which bin has the most marbles of a certain color. In database administration, this task is known as relational division.

Example

Input marbles (flexible format, this is just one possibility):

red,A
blue,B
green,C
red,B
red,A
blue,A

Input color:

red

Program output:

A

Format

Each 'marble' is represented as a (color, bin) pair, so the entire database of marbles is represented by a list of these pairs. The list can be fed into your program in any reasonable way so long as the association of the input data remains between colors and bins -- for example via CSV on stdin in color,bin pairs split on newlines in string-manipulation programs, or perhaps via a list of (str, str) tuples as a parameter to a function in a language like Python. It's up to you.

In my examples, I'm using strings to represent colors and bins, but you can use any data type that is capable of representing at least 1000 distinct values in your programming language (i.e. no booleans). Examples of other acceptable data types would be integers or floats so long as you're consistent.

It's very important that colors cannot be used as bins, and bins cannot be used as colors (i.e. the set of bin identifiers and the set of color identifiers must be disjoint). If this isn't true, the result is undefined.

In addition to the marble database, your program takes in a color identifier, again in whatever way is most convenient to do I/O of a single value in your language. Your program must output or return a unique identifier for the bin that contains the most marbles of that color.

The result is undefined if the input color doesn't exist, or if there is a tie between multiple bins (i.e. if the input color is red, there are 70 red marbles in total, and two bins both have 30 red marbles). Your program should be expected to handle up to 1000 input marbles without much difficulty.

This is a challenge, so the shortest program wins, with submission time (earlier is better) as the tiebreaker.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ If it's a function, it must output to stdout too? Huh? \$\endgroup\$ – user202729 May 3 '18 at 1:28
  • \$\begingroup\$ @user202729 Thanks, bug fixed! \$\endgroup\$ – Harry May 3 '18 at 3:10
1
\$\begingroup\$

Conway's Battlegrounds


Conway's Battlegrounds will be a mix of PUBG and Conway's Game of Life. In this challenge, you will need to make a Python bot that will play it.

Game rules

The controller, at the beginning of the round, will create a two-dimensional 500x500 toroidal (edge wrapping) board with chosen cells being alive, the others are dead.

The players are then separated into equal teams, each with 4 bots. If there isn't enough players in the team, some of them might be duplicated.

Gameplay

"Parachuting" phase

Everybody in the game will be given the array representing the starting state of the board. Each bot's class will be initialized, with these arguments in order:

  • num - an int between 2 and 5 inclusive, representing the number you'd be marked with on the map during the game. The other numbers in the range will be your party members.
  • area - Dictionary, where each key is a 2 value tuple (x,y) and each value is either a 0 (dead cell) or 1 (alive cell)

During this phase, each bot's method parachute will be called exactly 10 times. It will be given only one argument:

  • team - 4 item dictionary with your and each teammate's ID (between 2 and 5) as key and a 2 item tuple as value, representing the (x,y) position they chosen, or None if they didn't yet chose any.

The method can return a 2 value tuple, representing where the bot want to start or None, if the bot can't decide. The returned value will be visible to every other teammate.

The method will be called again, even if the player already chose a location. The next return value will replace previous. You can prevent that by returning team[self.num], assuming you saved the num parameter from __init__.

It is recommended to spawn your bot near teammates, so it's easier to cooperate later.

If the method has been called the 10th time and the bot didn't return that time a (int, int) tuple, it will be removed from the game.

Each bot will then be spawned at a random location in a 9x9 rectangle, with the returned location in the center. The bot will not collide with other players.

Starting phase

This phase will take exactly 25 turns. It's almost the same as the later, main phase of the game, except that no cell will die or be created in it.

The start method of each bot will be called once every turn. It will take these arguments in order:

  • area - Basically the same as in the previous phase, but with several modifications:
    • It will be only a 25x25 fragment of the map, with the bot in the middle.
    • It might also contain the ints in range 2..5 representing each teammate.
    • It might also contain the int -1 representing an opponent.
  • turn - The number of the turn, starting with 0. In the last turn of the phase it will be 24.
  • chat - a list of new chat messages, stored in tuples (author_id, msg_id)

The method must return a 0..4 value tuple or list, which may contain up to three actions the bot will perform during it and optionally a single chat message. Each item in tuple is a one move, depending on the value:

  • Falsy values (0, None, False) - Do nothing
  • Positive int - Move in given direction, according to the rule (where the bot is in the center):

    1 2 3
    4   6
    7 8 9
    

    Bot can only move to a neutral position.

  • Negative int - Replace a neighbour dead cell with a neutral alive cell, according to the rule above, ex. -1.
  • String - Send a chat message with the given ID, explained later

Main phase

Similar to the previous phase, but in this one, cells can die. It won't end until only one team is on the board.

The main method of each bot will be called once every turn. It will take these arguments in order:

  • area - Same as in starting phase
  • team - Dictionary with position of teammates id: (x, y)
  • turn - The number of the turn, starting with 0. In the last turn of the phase it will be 24.
  • hp - The amount of health points the bot has, explained later. Initially 4.
  • chat - a list of new chat messages, stored in tuples (author_id, msg_id)

The return value is the same as in the previous phase.

Neighbours, dying and reproducing

  • A neighbour of a cell a is an another cell that is positioned next to the cell a, either orthogonal or diagonal.
  • A neutral cell is any cell that is either 0 or 1 (isn't a bot).
  • A bot cell is any cell occupied by a bot, that is, the negative number -1 and positive 2, 3, 4, 5.
  • A dead cell is any cell that is exactly 0.
  • An alive cell is any cell that is not dead (0). This includes both bot cells and 1's.

In this round, cells can die. They can also reproduce.

  • Neutral cells (marked 1) will die (turn to 0) if amount of their alive neighbours is not 2 nor 3.
  • Dead cells (marked 0) will reproduce (turn to 1) if amount of their alive neighbours is exactly 3.

Rules about bot cells (-1 and greater than 1) are a bit different though.

  • Bot cells will lose 1 hp if amount of their alive neighbours is not 2 nor 3 and no natural cells were reproduced in the neighbourhood.
  • Bot cells will die if they have 0 hp.
  • Bot cells will gain 1 hp if amount of their alive neighbours is equal to 3 and at least 1 neighbour is a teammate. Cell will not gain hp if it has 3 or more hp.
  • Bot cells will be moved if amount of their alive neighbours is not 2 nor 3 and a single nearby cell was reproduced (it will replace it). Bot cells cannot duplicate.

The red zone

Every 100 generations (turns), the red zone will start in the place with most dead cells. It will end after 10 turns, and every second turn it will spawn a glider.

Chatting

Bots in the same team can communicate between themselves during the game.

Some of the messages were made because of how the board is generated. Make sure you read this before, so you can use it to collaborate with other bots easier.

Here's a list of all "built-in" messages:

  • 1 - Help!
  • 2 - Wait!
  • 3 - Need healing!
  • 4 - Come here
  • 5 - Enemies are nearby
  • 6 - I'll fight
  • 7 - I'll build
  • 8 - Search for boats/Build a boat
  • 9 - Get in the boat
  • 10 - Exit the glider

The controller

WIP, I won't probably have time to make it this week.

Example bot

A classic random bot, won't survive long.

import random


class RandomBot:

    def __init__(*args): pass

    def parachute(self, team: dict):

        return random.choice([x for x in team.values() if x])

    def start(*args):

        return random.randint(-9, 9)

    def main(*args):

        return RandomBot.start()

Additional rules

  • You have access only to non-superuser built-in Python packages
  • You must not create, write nor open any files
  • You cannot access any of internal or other bot's classes
  • You cannot modify any mutable arguments given to your methods, only their copies
  • You shouldn't throw any exceptions
  • You must return only specified values.
  • The code you publish here must not output anything
| |
\$\endgroup\$
  • \$\begingroup\$ During the parachute phase, the team[self.id] should be that bot's last return value, and the other values should be the other teammates in the same order as their ids. \$\endgroup\$ – SIGSTACKFAULT May 7 '18 at 18:28
  • \$\begingroup\$ You say that bots are given Ids from 2 to 6 inclusive with a team of size 4. However, there are 5 values in the range 2 to 6 inclusive. \$\endgroup\$ – Kamil Drakari May 7 '18 at 18:46
  • \$\begingroup\$ @KamilDrakari I noticed that earlier, but somehow didn't edit it in. Thank you! \$\endgroup\$ – RedClover May 7 '18 at 19:05
  • 1
    \$\begingroup\$ I think it needs to be made clearer that the Game Of Life part of this challenge essentially treats all bot locations as "alive" cells. So the location of a bot is relevant for cells spontaneously becoming alive, the bot loses HP in situations where a cell would die, etc. That was the impression that I got, but it didn't immediately "click". Moving the bot if an adjacent tile reproduces and the bot would otherwise take damage is unintuitive, but I guess there's probably a good reason for it. \$\endgroup\$ – Kamil Drakari May 7 '18 at 19:23
  • \$\begingroup\$ @KamilDrakari I edited the challenge to make it more clear. Originally, the reason for bots moving instead of taking damage was to allow the existence of vehicles, but as I look on the challenge now, I think I screwed it up, because a vehicle (glider) won't be any faster than the cell itself. Unless I increase amount of generation between turns \$\endgroup\$ – RedClover May 8 '18 at 11:34
  • \$\begingroup\$ @Soaku I don't think having multiple generations between turns sounds fun, and it adds some extra weirdness to taking damage (either you can take damage multiple times with no way to act, or you lose the "take damage any time your cell would die" symmetry). I think losing the vehicles is a better tradeoff. \$\endgroup\$ – Kamil Drakari May 8 '18 at 12:37
  • \$\begingroup\$ @KamilDrakari I know. So given that, the rule doesn't make any sense now. \$\endgroup\$ – RedClover May 8 '18 at 12:48
1
\$\begingroup\$

Nice Tile Connector

Your task is to connect the tiles given to you in the input by removing the lines on sides they connect

Input

A set of tiles that are not yet connected

Output

The tiles with the walls removed in the right places to connect them

Method

Each tile in the input looks like this:

___
|~|
|_|

Every air space looks like this:

...
...
...

On a tile, the top line is in front of the side lines, which are both in front of the bottom line. That means the top line will always replace the | characters that would be there on the sides, and the side lines will always replace the _ characters that would be there on the bottom.

Each tile must have any lines removed that are adjacent to other tiles

Example

The input

...______...
...|~||~|...
...|_||_|...
...___...___
...|~|...|~|
...|_|...|_|
...______...
...|~||~|...
...|_||_|...

The output

...______...
...|~~~~|...
...|~~__|...
...|~|...___
...|~|...|~|
...|~|...|_|
...|~~___...
...|~~~~|...
...|~~~~|...

As this is , smallest solution in bytes wins.

| |
\$\endgroup\$
1
38 39
40
41 42
95

You must log in to answer this question.

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