525
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

If you think one of your posts needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3361 Answers 3361

1
12 13
14
15 16
113
3
\$\begingroup\$

Atomic Handshakes

Introduction

Here you are. At a party, with two drinks in your hands. Your friend just went to the bathroom and you don't really know anyone else here. And so you wait. Or do you?

There is a century old hypothesis known as Six Degrees of Separation. The hypothesis states, that any other person in the world is connected to you as a friend of a friend of a friend etc.. It would essentially only take you six handshakes to connect with any other person on this planet. But is there actually any truth in this hypothesis? That's what we're about to find out in this challenge!

A similar question also finds its way into my own field of expertise: chemistry. Hence the title. Chemistry is the study of molecules, and molecules get very complex very fast. All (for the sake of simplicity) atoms in a molecule are connected. For certain types of analysis, one may need to know how many connections (bonds) it takes to get from one atom to another.

The Challenge

In a set of N people, each person has a maximum of N-1 direct connections. Based on this information, it is your task to deduce for every person what the lowest number of connections is to get to every other person.

People (and atoms too) can have similar names. Therefore, instead of a name, every person will get a unique identifier. To make things easy, the identifier will be a non-negative integer and the integers are all consecutive. How convenient!

Input

An array-like object of size N which lists the first-degree connections for each person.

Output

A two-dimensional, symmetrical array of size NxN which shows for each person the shortest distance to every other person.

Challenge rules

  • All people are connected: there are no loners or isolated groups in the input
  • Circular connections are allowed, but
  • Only the shortest connection must be output as more ways lead to Rome

General rules

Examples

As the theory may still be somewhat confusing, I will include a network graph for each example. This should make it a lot easier to understand what we're talking about. Here goes!

Example 1

Consider the connected set

0---1---2---3
        |   |
        4---5---6

For this network, our input array will be

[[1]          # Since 0 is connected only to 1
 [0 2]        # Since 1 is connected to 0 and 2
 [1 3 4]      # Since 2 is connected to 1, 3 and 4
 [2 5]        # Et cetera
 [2 5]
 [3 4 6]
 [5]]

Which should result in the following output (excluding comments):

# Distance from
# 0 1 2 3 4 5 6
                   # To
[[0 1 2 3 3 4 5]   # 0
 [1 0 1 2 2 3 4]   # 1
 [2 1 0 1 1 2 3]   # 2
 [3 2 1 0 2 1 2]   # 3
 [3 2 1 2 0 1 2]   # 4
 [4 3 2 1 1 0 1]   # 5
 [5 4 3 2 2 1 0]]  # 6

Example 2

Consider the connected set

.-------.
|       |
|   0   |
|   |   |
|   1---2---3---.
|   |   |   |   |
'---4---5---6   |
    |           |
    7---8---9---'

For this network, our input array will be

[[1]          # Since 0 is connected only to 1
 [0 2 4]      # Since 1 is connected to 0, 2 and 4
 [1 3 4 5]    # Since 2 is connected to 1, 3, 4 and 5
 [2 6 9]      # Et cetera
 [1 2 5 7]
 [2 4 6]
 [3 5]
 [4 8]
 [7 9]
 [3 8]]

Which should result in the following output (excluding comments):

# Distance from
# 0 1 2 3 4 5 6 7 8 9
                         # To
[[0 1 2 3 2 3 4 3 4 4]   # 0
 [1 0 1 2 1 2 3 2 3 3]   # 1
 [2 1 0 1 1 1 2 3 3 2]   # 2
 [3 2 1 0 2 2 1 3 2 1]   # 3
 [2 1 1 2 0 1 2 1 2 3]   # 4
 [3 2 1 2 1 0 1 2 3 3]   # 5
 [4 3 2 1 2 1 0 3 3 2]   # 6
 [3 2 3 3 1 2 3 0 1 2]   # 7
 [4 3 3 2 2 3 3 1 0 1]   # 8
 [4 3 2 1 3 3 2 2 1 0]]  # 9

Example 3

Consider the connected set

.---0---.
|   |   |
1---2---3
|   |   |
'---4---'

For this network, our input array will be

[[1 2 3]      # Since 0 is connected to 1, 2 and 3
 [0 2 4]      # Since 1 is connected to 0, 2 and 4
 [0 1 3 4]    # Et cetera
 [0 2 4]
 [1 2 3]]

Which should result in the following output (excluding comments):

# Distance from
# 0 1 2 3 4
               # To
[[0 1 1 1 2]   # 0
 [1 0 1 2 1]   # 1
 [1 1 0 1 1]   # 2
 [1 2 1 0 1]   # 3
 [2 1 1 1 0]]  # 4
\$\endgroup\$
1
  • 2
    \$\begingroup\$ In short, all pairs shortest path. Single-route shortest path would definitely be closed as a duplicate; I would say there's a significant chance that the consensus will be that this is also a duplicate of one of the questions in path-finding. \$\endgroup\$ – Peter Taylor Jul 5 '19 at 10:59
3
\$\begingroup\$

Too many spies

You are fighting an extensive network of enemy spies. You know that each spy has at least one (sometimes multiple) fake identities they like to use. You'd really like to know how many spies you're actually dealing with.

Luckily, your counter-intelligence agents are doing their job and can sometimes figure out when two fake identities are actually controlled by the same enemy spy.

That is to say:

  • Your agents don't always know when two fake identies have the same spy behind them, however
  • If an agent tells you two fake identities are controlled by the same spy, you trust they are right.

Agent messages

Agents send you cryptic messages telling you which identities have the same spy behind them. An example:

You have 2 agents and 5 fake identities to deal with.

The first agent sends you a message:

Red Red Blue Orange Orange

This means they think there are 3 spies:

  • the first one (Red) controlls identities 1 and 2
  • the second one (Blue) controlls identity 3
  • the third one (Orange) controlls identities 4 and 5

The second agent sends you a message:

cat dog dog bird fly

This means they think there are 4 spies:

  • the first one (cat) controlls identitiy 1
  • the second one (dog) controlls identities 2 and 3
  • the third one (bird) controlls identity 4
  • the fourth one (fly) controlls identity 5

Compiling the intel we see:

Identities:   id1    id2    id3    id4    id5 
Agent 1:    |--same-spy--|       |--same-spy--|
Agent 2:           |--same-spy--|
Conclusion: |-----same-spy------||--same-spy--|

This means there are at most 2 spies.

Notes

Identities owned by the same spy do not have to be consecutive, i.e. a message like:

dog cat dog

is valid.

Also, the same word might be used by two different agents - that does not mean anything, it's just a coincidence, e.g.:

Agent 1: Steam Water Ice
Agent 2: Ice Ice Baby

Ice is used by both agents - the Ice used by the first agent is unrelated to the two occurences of Ice used by the second agent.

Challenge

Compile all your agents' intel and figure out how many enemy spies there really are. (To be more precise, get the lowest upper bound, given the limited information you have.)

The shortest code in bytes wins.

Input and Output spec

The input is a list of n lines, which represent n messages from agents. Each line consists of k space-separated tokens, same k for all lines. Tokens are alphanumeric, arbitrary length. Case matters.

The output should be a single number, representing the number of distinct spies, based on your agents' intel.

Examples

Example 1

Input:

Angel Devil Angel Joker Thief Thief
Ra Ra Ras Pu Ti N
say sea c c see cee

Output:

2

Example 2

Input:

Blossom Bubbles Buttercup
Ed Edd Eddy

Output:

3

Example 3

Input:

Botswana Botswana Botswana
Left Middle Right

Output:

1

Example 4

Input:

Black White
White Black

Output:

2
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The core problem of union set is nicely presented, but the input requirements are rather too restrictive. The question will be better received if the input is permitted to be received as an array of arrays or any other reasonable list format. See codegolf.meta.stackexchange.com/q/7853/194 \$\endgroup\$ – Peter Taylor Jul 16 '19 at 8:22
3
\$\begingroup\$

Originally posted on main site, moved here for more suggestions. Better scoring mechanics required.

Introduction

I've been browsing all those challenges and was thinking "yeah, they're good, but what if we make GoL one?", so here it goes.

Challenge

Build starting setting for either Conway's Game of Life or other similar cellular automaton (restricted to ones with binary cell state) which after known amount of generation will include square area containing representation of QR code decodable to string "Hello, world!".

  • Cell (non-empty state) is interpreted as black pixel, no cell as white.
  • Your automation should take at least one generation until result (no hardcoded results allowed).
  • Your automation operates on infinite board.
  • Not sure if this option will be useful, but you can specify scaling ratio: single integer, setting side of square encoding single pixel. Pixel's color is color of cell dominating by count in it (you can specify 50/50 edge case resolution in your answer). Obviously, in this case side of output area should be proportional to scaling ratio. This option doesn't affect scoring.
  • It's not necessary, but nice to provide either link to online demo or .rle file.

Example result

enter image description here

Decodes to "Hello, world!"

Scoring

Your score is calculated as

score = (initial amount of cells)^2*(number of generations until result) + (number of cells out of output area)*5

Lower score is better.

Happy GoLfing!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ I think this challenge is interesting, although I suggest that the scoring criterion be a combination of the number of initially on cells and the number of generations necessary to get to the final output, without counting the number of on cells in the output (otherwise there's an aspect of QR code golf in the challenge as well, which complicates matters more). Also, I don't really understand the 4th bullet point. Finally, you seem to want to allow different binary cellular automata to compete, just like different languages. Is this true? \$\endgroup\$ – Erik the Outgolfer Jul 14 '19 at 22:48
  • \$\begingroup\$ @EriktheOutgolfer Why would including amount of cells out of output area be bad? It only counts cells which aren't part of QR code, so it seems acceptable. 4th point may probably need some illustrations to make it easier to get (or just remove that). You got the last part right. \$\endgroup\$ – val is still with Monica Jul 14 '19 at 23:34
  • \$\begingroup\$ Oh, I misread the "out of output" part. So you allow extraneous on cells outside of the QR code with a penalty? \$\endgroup\$ – Erik the Outgolfer Jul 14 '19 at 23:36
  • \$\begingroup\$ @EriktheOutgolfer I think that is more or less fine to have some cells on field as long as output in specified area is correct by itself. \$\endgroup\$ – val is still with Monica Jul 14 '19 at 23:37
  • 2
    \$\begingroup\$ Could you clarify what classes of automata are eligible? You've specified only binary (two possible cell states). What neighbourhoods are valid? Only the standard 3 by 3 Moore neighbourhood, or also other size and shape neighbourhoods like Von Neumann neighbourhoods? Must all cells in the neighbourhood contribute equally to the outcome (a totalistic automaton) or can different patterns of the same number of "on" cells give different results? \$\endgroup\$ – trichoplax Jul 16 '19 at 21:06
  • 1
    \$\begingroup\$ Where you choose to draw the line is entirely up to you, but it could have a large effect on the nature of the challenge. For example, if arbitrary size and shape neighbourhoods are allowed, with rulesets based on the arrangement of "on" cells rather than just how many are "on", it may be possible to choose a ruleset that gives the output in a single step (maybe - I haven't thought it through). Whether you see that as a bad thing or an interesting way of solving the challenge will determine how restrictive you choose to be. Personally I'd stop short of allowing quite that much flexibility... \$\endgroup\$ – trichoplax Jul 16 '19 at 21:09
  • \$\begingroup\$ Is there a standard for QR that avoids all disagreement as to what's a valid code? On further thought, it might be better just to requre a fixed output pattern, like some pixel version of Heelo World, and not have the whole QR layer. \$\endgroup\$ – xnor Jul 16 '19 at 21:35
  • \$\begingroup\$ In particular, following @xnor's comment, does "decodable to" mean that errors are allowed as long as they're below the threshold for correction? \$\endgroup\$ – Peter Taylor Jul 17 '19 at 10:55
3
\$\begingroup\$

How long's left?

Posted here.

\$\endgroup\$
6
  • \$\begingroup\$ Shouldn't the third test case be FifTy Nine MiNutes And ForTy Six SeConds? \$\endgroup\$ – Erik the Outgolfer Jul 9 '19 at 19:26
  • \$\begingroup\$ @EriktheOutgolfer Thanks, fixed \$\endgroup\$ – Geza Kerecsenyi Jul 9 '19 at 19:27
  • \$\begingroup\$ @Shaggy the challenge here isn't to calculate the number of syllables: it's to find the first number that has the same number of syllables as the distance from the current time. \$\endgroup\$ – Geza Kerecsenyi Jul 11 '19 at 21:14
  • \$\begingroup\$ Ah, OK, I get it now. Yeah, I think that's sufficiently different, so; ignore my previous comment! \$\endgroup\$ – Shaggy Jul 11 '19 at 21:17
  • \$\begingroup\$ Could you please clarify how many syllable each number has? (A list should help.) \$\endgroup\$ – tsh Jul 12 '19 at 7:38
  • \$\begingroup\$ @tsh done, see now. \$\endgroup\$ – Geza Kerecsenyi Jul 12 '19 at 15:05
3
\$\begingroup\$

Character Frequency in a String

Tags:

Posted here.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ i dislike the special case of space \$\endgroup\$ – Jo King Jul 21 '19 at 1:25
  • \$\begingroup\$ @JoKing If there was no special case for space, a string like 1 a would look something like 1 1; 1;a 1. Also, it's for the challenge. \$\endgroup\$ – bigyihsuan Jul 21 '19 at 3:19
  • \$\begingroup\$ I'm with @JoKing on this; nothing is added to the challenge by special-casing spaces. \$\endgroup\$ – Shaggy Jul 21 '19 at 21:08
  • \$\begingroup\$ I'd like to further say that restricting the output this much doesn't seem to add much to this challenge. Why isn't, for example, a list of pairs acceptable? I can't find any justification for your output rules. That's not to say you can't do it, but I have a hard time imagining it will be popular. \$\endgroup\$ – FryAmTheEggman Jul 22 '19 at 18:58
  • \$\begingroup\$ Related. \$\endgroup\$ – AdmBorkBork Jul 23 '19 at 20:15
  • \$\begingroup\$ @AdmBorkBork, having since given it a try in JS, I'm pretty sure there's a closer (potential) dupe target than that. \$\endgroup\$ – Shaggy Jul 23 '19 at 22:12
  • 3
    \$\begingroup\$ Having posted this, you should delete the sandbox post. \$\endgroup\$ – Adám Jul 24 '19 at 6:29
3
\$\begingroup\$

Golf range minimum queries of a list

, , and

Looks like this post hasn't gotten any problems called out, but also not that much support. If you could leave even a brief comment if you don't like it, that would be much appreciated.

(Inspired by the first problem solved in Stanford’s advanced data structures course.)

Despite the academicese-heavy name, the problem we're going to solve is almost unbearably simple.

We have a list of numbers.

[31, 41, 59, 26, 53, 58, 97]

We're going to cut some contiguous snippet out of that list of numbers.

[31, 41, 59, 26, 53, 58, 97]
    |41, 59, 26, 53|

And then we're going to find the minimum of that snippet. In this case, that's quite obviously 26. That's all.

And the obvious solution is pretty fast, too, with O(n) time and O(1) space in the size of the list:

minval = arbitrarily large value
for (i=first snippet index, i<last snippet index, i++)
  if (list[i]<minval) minval = list[i]

So what's with the ?

Where it gets interesting is when you try to see how efficient you can make it when you have a fixed list but a large number of range minimum queries -- snippets to find the minimum of. This version of the problem is useful, for example, if you have a huge time series you want to load only once, but you want to find the minimum of many different subintervals of that time series.

In such a scenario, it would actually be faster in practice to literally precompute all n**2/2 queries, store it in a table, and then just retrieve data from that table for an O(1) time and O(n**2) space solution. Dynamic programming solution from the Stanford slides ^dynamic programming solution taken from the Stanford slides

And then if you're clever enough, you realize that you only have to store each query with size that's a power of two -- you can just combine those power-of-two minima to sum to an arbitrarily sized query, and achieve the same results with constant time and linearithmic rather than quadratic space.

Interestingly, if you keep optimizing, you can get to an O(1) time and O(n) space solution using a sort of augmented list known as a Fischer-Heun structure. I'd love to go into the details of the structure here, but explaining how it weaves into Cartesian tree building on fixed-size snippets would make this question about 50 pages long. It's explained in the Wikipedia page linked in the title (which I've copied here), however, along with several faster-than-linear intermediate structures.

(If you can get past a research paywall, here's the original Fischer & Heun 2011 paper. And if you’d prefer the much more verbose but much more hand-holdy Stanford lecture style, here are the follow-up slides that goes into this solution, including lots of intermediates.)


The challenge

You can either write a full program or a function that calculates the result of a series of range minimum queries given a fixed list. Scoring is set up such that in general, the shortest and most-efficient-over-lots-of-queries code wins.

Input:

A list of integers xs, followed by a series of i, j pairs denoting the start and end of the snippet, inclusive (so the 26 example above uses indices i=1 and j=4). The list of integers is guaranteed to have at least one integer, and 0 <= i <= j < len(xs). This can be taken in any format that works best for your language — for example, one list for xs and one list of tuples for the i, j pairs; or maybe all the different pairs as a variable number of arguments. For a full program that takes in input from stdin, I’ll fix a format for the input:

xs[0] xs[1] xs[2] xs[3] ...
i1 j1
i2 j2
i3 j3
...

Output:

An ordered collection of the range minima for each i, j query, in the same order that they were given. In case an unordered map (such as a Python dictionary) from each i, j query to its range minimum works better for your language, that will also be allowed as an output; as long as it's obvious which minimum is related to which query.

Once again, for a full program that prints to stdout or a file, I’ll fix the format to have each range minimum on each newline (trailing newlines permitted).

Scoring:

Lower score is better; score is determined by

at(b)^2+as(b)

Where b is the byte count of your code, at is the asymptotic runtime Ө(n) of the algorithm in the size of xs interpreted as a function of n, and as is the asymptotic space usage Ө(n) in the size of xs interpreted as a function of n.( All constant coefficients in such Ө(n) expressions must be 1, and only the fastest growing term may be kept in expressions, as is standard.)

Therefore, the above pseudocode solution, which uses Ө(n) time and Ө(1) space, and is 126 characters, would have a score of (b => b**2 + 1)(126)=15876+1=15877. (Of course, the pseudocode isn't really valid since it's missing a construct to deal with multiple queries, and also because it's uncompilable pseudocode...)

Test cases:

Input:

31 41 59 26 53 58 97
1 4
0 2
5 6

Output:

26
31
58

Input:

1
0 0
0 0

Output:

1
1

Input:

-4 28 31 -54
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3

Output:

-4
-4
-4
-4
28
28
-54
31
-54
-54

Sandbox Questions:

  • Would the asymptotic runtime count as a non-observable requirement?

  • is this too long and/or abstruse lol

  • I’m not sure how to word the scoring section to narrow down the most obvious, basic O(n) expression — an algorithm that’s Ө(n) is also Ө(n/16384-50000) by definition. Is what I have clear enough? Have I left any loopholes?

  • I kind of wanted to encourage people to try to implement Fischer-Heun or one of the more time-efficient intermediates in the slides, without restricting them to one particular algorithm (e.g. challenge: you have to make a Fischer-Heun structure). Does the scoring system make sense for this? Is it fair to have, for example, a Jelly answer using the naive algorithm in 3 bytes (score 10) compete with a Jelly answer using the Fischer-Heun structure in 30 bytes (score 31); but a naive Python answer with score 3000+ compete against with a Python Fischer-Heun with score 300?

\$\endgroup\$
1
  • 3
    \$\begingroup\$ [tag:tag-name] \$\endgroup\$ – Adám Jul 30 '19 at 19:06
3
\$\begingroup\$

Irish Snap: Variant Rules

Introduction

Recently, me and a couple of my friends decided to play some cards, and one of them suggested the game 'Irish Snap', which was the inspiration for this challenge. However, I later learnt that the game has a lot of different rules that work ,some of which are listed here. The rules that are in this challenge aren't currently listed on that page, hence the name, 'Variant Rules'

The Challenge

Given an array of 3 cards, output a truthy or falsey value depending on if they make a valid snap in a game of Irish snap.

Input

The input will be an array of 3 numbers, ranging from 1-13 inclusive, with 11 being jack, 12 being queen and 13 being king. The last number in the array will be the number at the top of the stack of cards.

Rules

The 4 different criteria for if cards make an Irish snap are a snap:

  • The top and middle cards are the same
  • The top and middle cards have a difference of one
  • The top and bottom cards are the same
  • The top and bottom cards have a difference of one

If any of these criteria are met, you must output a truthy value. As well as this, for the two criteria that require the cards to have a difference of one, it 'wraps around', meaning that an ace and a king are considered to have a difference of one, and vice versa.

Test Cases

Input -> Output
1 13 7 -> False
1 4 13 -> True
9 3 6 -> False
8 9 7 -> True
2 6 5 -> True
12 5 11 -> True
10 4 8 -> False
12 13 7 -> False
9 7 10 -> True
7 3 1 -> False
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Wikipedia describes a substantially different game under the same name. Is there any less ambiguous name for this? \$\endgroup\$ – Peter Taylor Aug 6 '19 at 8:27
  • 1
    \$\begingroup\$ Although I don't think there is a less ambiguous name for it that I can find, the version I described is a combination of the alternate rules listed below the section you linked: 'conventional snap', 'runs', 'sandwiches' and the last rule I listed is basically a combination of 'runs' and 'sandwiches'. How could I change the name to reflect this? \$\endgroup\$ – EdgyNerd Aug 6 '19 at 8:38
  • \$\begingroup\$ Should I change the name to "Ultimate Snap", as that's what Wikipedia says those rules are commonly referred to as? \$\endgroup\$ – EdgyNerd Aug 6 '19 at 8:42
  • 1
    \$\begingroup\$ I think runs as described requires all three cards and in the right order. Maybe "Irish snap: variant rules" would be a suitable title, and the introduction can reference Wikipedia and say that the exact rules we'll be using aren't listed (at time of writing the question). \$\endgroup\$ – Peter Taylor Aug 6 '19 at 8:49
  • \$\begingroup\$ Ok, I've added in all of those suggestions \$\endgroup\$ – EdgyNerd Aug 6 '19 at 11:23
  • 1
    \$\begingroup\$ As our token Irishman, I endorse the keeping of "Irish Snap" in the challenge name! \$\endgroup\$ – Shaggy Aug 7 '19 at 21:22
  • \$\begingroup\$ Do you think I'll be able to post this now? \$\endgroup\$ – EdgyNerd Aug 20 '19 at 9:44
3
\$\begingroup\$

Truth Table Composition

Given 2 or more truth tables, output the "shortest" way to compose the first N-1 tables to form the last (Nth) table.

Rules

  • Standard loopholes/io rules apply.
  • Input is a "list" of truth tables
    • A truth table is a "list" of rows that contain the inputs and the corresponding output
      • The input will always be the same length for a given table
      • There must be \$ 2^N \$ rows in a given table, where N is the number of inputs in the table
      • Each row must have distinct input
      • Inputs and outputs must both be "booleany" e.g.:
        • true/false
        • 1/0
        • truthy/falsey
        • "Bob"/"Sally"
    • The input can be in any reasonable format.
      • Any of the formats shown here are reasonable.
      • Taking the output first (ie for &: 1,1,1;0,0,1;0,1,0;0,0,0) is reasonable.
      • Input that requires non-trivial logic to convert is not reasonable.
      • When in doubt, ask in the comments.
  • Output is a "nested structure"
    • Each level of the nest contains information of the:
      • Truth table that was used
      • The ordered inputs (of this structure)
    • If a node is a leaf (one of the inputs to the final truth table) it must:
      • Be distinguishable from the other nodes
      • Contain the index of the input to the final table
    • Output format must be reasonable (see details under input)
  • "Shortest" is measured by the number of nodes in the output structure.
  • It will always be possible to construct the last table with the first N-1.
  • You do not need to handle invalid input.
  • This is , so the answer with the smallest asymptotic time complexity wins! Answers that do not aim to be efficient are also welcomed.

Yes, I'm done with rules now. Sorry.

Test Cases

For these test cases, the output is explained below. Note that this is not the output format you have to use! - $N is the Nnt input to the final table (0-indexed) - N(...) is the Nnt input table applied to ... (also 0-indexed) - Arguments are comma separated and are in this format. - Note that N() is different from $N; the former is the Nnt truth table applied to nothing (only valid in the case of truth tables 1 and 0), and the latter is the Nnt input to the final table.

Input:
(anything)

1 0 0
0 1 1
0 0 0
1 1 1

Output:
$1 (length 1; leaf; gives the second input)
Input:
1 0
0 1

1 1 1
0 0 1
0 1 0
1 0 0

1 0 1
1 1 0
0 0 1
0 1 0

Output:
0($1) (length 2; the first table (not) applied to the second input)
Input:
1 0
0 1

1

0

Output:
0(1()) (length 2; the first table (not) applied to the second table (true))
Input:
0 1
1 0

1

1 0
0 1

Output:
0($0) (length 2; the first table (not) applied to the first input to the final table)
Input:
0 1
1 0

1 1 1
0 1 0
1 0 0
0 0 0

1 1 1
0 1 1
1 0 1
0 0 0

1 1 0
0 1 1
1 0 1
0 0 0

Output:
1(2($0,$1),0(1($0,$1))) (length 8; "(A | B) & !(A & B)")

Meta

I think more test cases are needed, but am unsure what to add.

This is my firstsecond challenge, so all feedback is welcome!

\$\endgroup\$
20
  • \$\begingroup\$ The idea is good, I think. I had trouble understanding at first read though, and didn't understand at all your $ things. I suppose $1 is the same as 1() but I'm not sure. Suggested test case: Input : (1,0;0,1) ; (1) ; (1,0;0,1) with Output : 0() and not 0(1()) or 1(0()). \$\endgroup\$ – V. Courtois Aug 13 '19 at 14:40
  • \$\begingroup\$ @V.Courtois $0 is the first input to the final table, $1, the second etc. 0(...) is the first input table, 1(...) is the second, etc. Any recommendations on a better format? \$\endgroup\$ – tjjfvi Aug 13 '19 at 14:43
  • \$\begingroup\$ @V.Courtois Added your test case, though 0() is not a valid output as (1,0;0,1) takes in 1 input, not zero, it should be 0($0) \$\endgroup\$ – tjjfvi Aug 13 '19 at 14:46
  • \$\begingroup\$ Do you mean $0 is the input on the first row of the output table? It got even more foggy... Plus, isn't a truth table's order meaningless? I mean, you even swapped the order of the rows in the last test case. And I just noticed now the # notation... Would you mind clarifying it all? Those signs are nowhere defined in the challenge ^^' \$\endgroup\$ – V. Courtois Aug 13 '19 at 14:52
  • \$\begingroup\$ OH ; and by re-reading all the text I saw that your & is strange: why does 0&0 get 1?? \$\endgroup\$ – V. Courtois Aug 13 '19 at 14:53
  • 1
    \$\begingroup\$ @V.Courtois The "&" is not an &, it is an iff/not xor \$\endgroup\$ – tjjfvi Aug 13 '19 at 14:54
  • \$\begingroup\$ Oh my bad then, I didn't know for this one. \$\endgroup\$ – V. Courtois Aug 13 '19 at 14:56
  • \$\begingroup\$ @V.Courtois Tomorrow I’ll revise the test case format \$\endgroup\$ – tjjfvi Aug 14 '19 at 0:38
  • \$\begingroup\$ @V.Courtois I explained & slightly revised the notation; is it clearer now? If you have any suggestions, they would be very welcome. \$\endgroup\$ – tjjfvi Aug 14 '19 at 12:30
  • \$\begingroup\$ Ah yeah, it looks clearer now. The test case of length 8 is really helpful in the process, too, for guys like me that in general read the test cases before reading what is the actual challenge about :) Let's hear other points of view about this challenge, for my part I don't see any problem now. \$\endgroup\$ – V. Courtois Aug 14 '19 at 12:38
  • 1
    \$\begingroup\$ You can remove the "Exception: if there are 0 inputs, there must be 1 row." line, \$2^0=1\$. \$\endgroup\$ – Erik the Outgolfer Aug 15 '19 at 22:16
  • \$\begingroup\$ For languages that support ND array, a ND array (each dimension has size 2) would be a natural representation of a N-ary truth table. \$\endgroup\$ – user202729 Aug 16 '19 at 4:44
  • \$\begingroup\$ In your example is "1 1 1" = "(1, 1) -> 1" or "1 <- (1, 1)"? \$\endgroup\$ – user202729 Aug 16 '19 at 4:46
  • \$\begingroup\$ Also: do you know any polynomial time solution to this problem? \$\endgroup\$ – user202729 Aug 16 '19 at 4:48
  • \$\begingroup\$ @EriktheOutgolfer shame. I'll fix that. \$\endgroup\$ – tjjfvi Aug 16 '19 at 13:16
3
\$\begingroup\$

Planting Steiner Trees

In the following we are talking about Steiner trees, which are similar to minimal spanning trees: The goal is connecting all nodes via some paths such that the resulting graph that is as short as possible. In contrast to minimal spanning trees when constructing steiner trees you can add additional nodes.

In the following we are talking about points in the real 2d plane and when we are talking about distances and lengths, we are talking about the euclidean distance.

Also, a graph will comprise a set of points where the edges are straight lines between pairs of those points. The length of a graph will be the sum of the length of all edges.

So a steiner tree is a shortest graph connecting all given points possibly with inserting additional points. The following image shows the difference between a minimall spanning tree (blue) and a steiner tree (red).

It is known that it is very difficult to find steiner trees.

enter image description here

Task

Write a program that accepts a list of 2d points and tries to find/approximate a steiner tree of minimal length connecting those points by possibly introducing more points. (It does not have to find the an actual steiner tree.)

The program should output a list of all the points (including coordinates) of the constructed graphs, a list of all edges (including their lengths), the total length of the graph and a graphical representation of the grap.

The program should have a running time of no more than about half a minute for each of the examples on a reasonable computer.

You should also explain how your algorithm works.

Scoring

The program must be evaluated on all the [NOT YET] given test cases. The score is the sum of the total length of all test cases. The lowest score wins.

Test cases

Square:
(0,0),(0,1),(1,1),(1,0)

Nonagon:
(cos(2*pi*a/9),sin(2*pi*a/9)) for a = 0,1,...,8

Ladder:
(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)

Meta: I need to find a good set of test cases. Suggestions are appreciated.

If you have any suggestions, feel free to edit/add. Any improvements of the text are appreciated too.

@El'endia Starman Pointed out some interesting n-gon configurations

\$\endgroup\$
1
  • 3
    \$\begingroup\$ It is known that Steiner trees for regular n-gons where 7 <= n <= 12 are simply the n-gon with one side removed. 4,5,6 all have interesting configurations though. \$\endgroup\$ – El'endia Starman Oct 31 '15 at 0:03
3
\$\begingroup\$

Shortest Persistent Object in 5-Char JS

The []+=` subset of JavaScript is known to be Turing-complete. A key part of the construction is obtaining persistent objects whose properties can be set and retrieved in a loop.

Most expressions won't evaluate to constant values. For example, [] != [] when compared by reference. However, some expressions, such as [].name, return the same object every time they are evaluated.

The Task

The following should hold when e is substituted with your submission:

  • (e) instanceof Object (this includes functions and arrays)
  • (e) == (e)

This is , so the shortest valid submission (measured in bytes) wins.

\$\endgroup\$
3
\$\begingroup\$

What's this constructed number's starter?

\$\endgroup\$
7
  • \$\begingroup\$ The confusing part is how you mix single and multiple digit numbers. \$\endgroup\$ – Beefster Sep 3 '19 at 16:44
  • \$\begingroup\$ @Beefster Could you elaborate on how that confuses you, so that I can try to address it? \$\endgroup\$ – caird coinheringaahing Sep 3 '19 at 17:49
  • 1
    \$\begingroup\$ "A concatenated number is a number that can be built this way through the use of the multiples of single digit numbers: 1,2,3,4,5,6,7,8,9 A.K.A an element in one of these 9 sequences" - I can see the pattern in the example, but this is not very friendly to skimming. Maybe explain what is going on the 3 example? The other thing is that this doesn't really feel like it needs to be limited into multiples of 1 digit numbers. \$\endgroup\$ – Beefster Sep 3 '19 at 20:47
  • \$\begingroup\$ @Beefster I'll explain through the 3 sequence to make it clearer. It doesn't need to be limited to 1 digit numbers, although that guarantee that no element will ever be in more than 1 sequence, and is just how I decided to write the challenge. \$\endgroup\$ – caird coinheringaahing Sep 3 '19 at 21:17
  • 2
    \$\begingroup\$ I think you might try to find another name (or maybe do not name it at all) for "concatenated number" to avoid the possible confusion of concatenating single and multiple digit numbers. The recurrence is a much clear definition of such sequences and I think that should be put at the very beginning of the description. \$\endgroup\$ – Joel Sep 3 '19 at 23:13
  • \$\begingroup\$ "Is this clear enough? Is it easily understand what a concatenated number is?" Completely clear imo, although I agree with @Joel: \$10a + b\$ isn't really concatenating, so the title is a bit confusing for multi-digit numbers later on in the sequences. "Any other tag suggestions?" [sequence] maybe? And [integer] perhaps, although probably not; [number] would be enough here, and whether you'd use an [integer] or [string] is up to the user. "Is this a duplicate?" Couldn't find anything like it. "Any further feedback?" Some (large) test cases would be nice. \$\endgroup\$ – Kevin Cruijssen Sep 4 '19 at 7:30
  • \$\begingroup\$ @Joel I've changed the name to constructed numbers, as it should avoid any confusion and still makes it easier to refer to numbers that meet the criteria \$\endgroup\$ – caird coinheringaahing Sep 4 '19 at 9:06
3
\$\begingroup\$

43 quintillion permutations

\$\endgroup\$
8
  • \$\begingroup\$ I think the requirement for 1:1 mapping is a bit much. I think it would be much more reasonable to only require that there is at least one numeric representation for every possible permutation and that every whole number corresponds to exactly one permutation. I can't even begin to wrap my mind around a solution that ensures there are no duplicate states on the way up to 43-whatever quintillion, but I can think of a few that could theoretically encode any permutation, but with duplicates in the mapping. \$\endgroup\$ – Beefster Dec 11 '18 at 22:20
  • \$\begingroup\$ More on "every whole number corresponds to exactly one permutation" - the number of permutations of a rubik's cube requires a minimum of 66 bits to represent, so arbitrary-length integers are already a requirement to implement this challenge, therefore it is totally reasonable to need arbitrarily long integers to represent all permutations. \$\endgroup\$ – Beefster Dec 11 '18 at 22:23
  • \$\begingroup\$ @Beefster I have been toying with the idea of converting this to a code challenge, where your score is the number of unique permutations you are able to output. \$\endgroup\$ – caird coinheringaahing Dec 11 '18 at 22:51
  • \$\begingroup\$ The issue with that is that it's trivial to cover all the permutations by associating each bit in the binary representation as whether or not to rotate a certain side 1-quarter turn clockwise. The other issue is that it's very difficult to calculate the minimum number needed to represent all permutations for any given algorigthm. I like the idea of making it a code challenge better than code golf, but I can't think of a good criteria either. \$\endgroup\$ – Beefster Dec 11 '18 at 23:05
  • \$\begingroup\$ I think with a few minor clarifications this would be a great code golf challenge; I think it'd be great to see a non-golfed example program to show how it can be done. Also, as Beefster pointed out, a 64bit int cannot represent all required numbers, does you don't have to worry about the practicalities of actually taking in inputs greater than your language can handle mean I can still use a 64-bit int? Can I use a signed 64-bit int (assuming that makes the code shorter for some reason). \$\endgroup\$ – Shelvacu Aug 19 '19 at 10:06
  • \$\begingroup\$ Additionally, what are the restrictions on display? Do I have to use the colors WGRBOY? Can I display the cube flipped for some numbers? (W center on bottom, Y center on top, etc) Can I display it rotated? \$\endgroup\$ – Shelvacu Aug 19 '19 at 10:09
  • \$\begingroup\$ @Shelvacu The idea I'm trying to get across is that due to the potential size of the input, answers don't have to actually perform correctly for each and every input, assuming that the reason why they don't perform correctly is because the input is outside whatever limit the language/type has. So if a Javascript answer works perfectly for all inputs between 1 and 2^53-1, but fails for 2^53 because the input is out of bounds for Javascript, that's completely fine. If it failed for 2^53 because the algorithm used breaks after that many inputs, that's not fine. \$\endgroup\$ – caird coinheringaahing Aug 19 '19 at 10:27
  • \$\begingroup\$ @Shelvacu I'll loosen and clarify the output restrictions in the post itself \$\endgroup\$ – caird coinheringaahing Aug 19 '19 at 10:27
3
\$\begingroup\$

Cleaning the dishes

In this task, you will be given a bar of soap with a width of 1 or more units, which will be inputted as an integer. You will also be given a plate, which you will have to clean, using the soap as few times as you can. The plate will be inputted as a an array of 2 different characters, one of which is the 'dirty' character, and one of which is the 'clean' character. The plate will be at least 1 character. You will have to output an array with the 'clean' character representing the plate, and a third unique character to represent in what positions the bar of soap was placed. None of these 3 unique characters may be whitespace.

How much the soap cleans:

n//2-1 on each side for odd n
n//2-1 on the left side of the soap bar for even n
n//2   on the right side of the soap bar for even n

Input

An integer greater than or equal to 1. A series of 2 unique characters to represent clean portions and dirty portions. Here, '=' represents a dirty portion, and '-' represents a clean portion. '+' represents where the soap was placed.

IN : OUT

3 ===- : -+--
32 ================================ : ---------------+----------------
1 ==== : ++++
5 ----- : -----
4 -====- : --+---
3 -====- : --+-+-
7 === : +--
6 - : -
6 -==-===- : ---+----
5 -==--==- : ---+--+-
3 -==--==- : --+--+--

Rules

  • There are multiple solutions. Any one of them are acceptable, as long as they use the soap the minimum amount of times possible.
  • This is a contest, so the shortest answer in bytes wins!
  • The plate may only be non-whitespace characters, and have 2 unique characters.
  • The soap may only be one non-whitespace character, unique from the other 2 used in the plate.
  • Standard loopholes are not allowed.

Posted: Cleaning the dishes

\$\endgroup\$
4
  • \$\begingroup\$ If "soap input may only contain the characters '0' through '9', and may be multiple characters", then can it not be passed as an integer argument to a function? \$\endgroup\$ – Unrelated String Sep 4 '19 at 4:15
  • 1
    \$\begingroup\$ i already specified rules about soap input in the first paragraph, so i will erase that rule. \$\endgroup\$ – girobuz Sep 4 '19 at 20:34
  • \$\begingroup\$ There seem to be multiple possible outputs, e.,g.: 3 =-=-= could be either +--+- or -+--+, yes? If that is true, can we output any of them? \$\endgroup\$ – Chas Brown Sep 7 '19 at 23:34
  • \$\begingroup\$ Yes, any output is acceptable, as long as it works, and is the minimum. \$\endgroup\$ – girobuz Sep 7 '19 at 23:53
3
\$\begingroup\$

Battleship KotH

This is a pretty rough idea to start but I figured I would drop it in the sandbox so that people can start to think about it and I will remember to do it.

The idea here is a that combines the game, battleship with .

The rough idea is that two enemies would face off, each turn irradiating a location in their opponents source code. Then the opponents source code would be recompiled and then try and attack back.

Some additional thoughts I've had:

  • We will likely want to limit the size of the board to a specific rectangular size

  • I would like there to be a feedback from shooting your opponent (in the game battleship this is hit/miss) so that you are doing more than just firing randomly. Perhaps programs might irradiate a single bit (flipping its value) and get back its value before it was irradiated.

Language choice is a bit tough since I would like something multipurpose and flexible but I don't want to have to deal with the security issues that are involved in compiling and running a fully featured programming language.

\$\endgroup\$
2
  • \$\begingroup\$ radiation-hardening tends to work best with deletion. This is going to need a maximum byte count to be fair, otherwise the best strategy is excessive amounts of whitespace and comments. Love the idea though. \$\endgroup\$ – Beefster Sep 17 '19 at 14:22
  • \$\begingroup\$ You don't actually have to limit yourself to a specific language on this one. It wouldn't be that hard to use a shell script to run whatever languages are available. One question though: is each program able to read the source code of the other or is each attack supposed to be blind? If you're worried about security, you could run the controller in a docker container or VM. \$\endgroup\$ – Beefster Sep 17 '19 at 14:26
3
\$\begingroup\$

Injection from two strings to one string

\$\endgroup\$
5
  • \$\begingroup\$ Do you think that a reasonably number of languages won't implement the following: convert the strings into numbers (e.g. treat each character as a base 128 digit) then give a resulting string of those two numbers joined by some other character? I haven't spent too long thinking about it but that seems very short in most languages. I suppose there are other variants though where you map characters to some subset and then join them. \$\endgroup\$ – FryAmTheEggman Sep 24 '19 at 20:42
  • 2
    \$\begingroup\$ @FryAmTheEggman I imagine the solution used is going to depend on the language: what builtins it has, if it's more high-level or low-level, etc. But there may well end up being a prevalent algorithm. \$\endgroup\$ – negative seven Sep 24 '19 at 20:57
  • \$\begingroup\$ Why strings? Lists of integers, (even restricted to a range) work as well but don't have the complexities that strings do when it comes to printables etc. I feel like the simpler challenge is going to be the better one. \$\endgroup\$ – Wheat Wizard Sep 26 '19 at 3:30
  • 1
    \$\begingroup\$ @FryAmTheEggman Don't worry, I've thought of a totally different approach that I think would be shorter for many languages. \$\endgroup\$ – xnor Sep 26 '19 at 4:46
  • 2
    \$\begingroup\$ @SriotchilismO'Zaic Restricting the character set seems to me like a reasonably simple detail, while making it about strings encourages creativity with string operations, converting to string representations, etc. Also, I personally think string input/output is much more appealing to look at and easier to consume than a list of numbers. \$\endgroup\$ – negative seven Sep 26 '19 at 14:38
3
\$\begingroup\$

Code Golf Measurer © 2019

Hexdumps used with xxd look something like this:

00000000: 666f 6f20 6261 7220 7370 616d 2065 6767  foo bar spam egg
00000010: 730a                                     s.

Your task is to convert a hexdump in this form in to the number of bytes used.

Rules:

  • Usual loopholes forbidden.
  • This is , so shortest valid answer in bytes wins.
  • You may or may not include the newline at the end of text (0a). This means that if the hexdump ends in a newline (0a), that input may have it's output reduced by one.
  • An empty input must output 0.

Test cases:

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 2120 4865  Hello, world! He
00000010: 6c6c 6f2c 2077 6f72 6c64 210a            llo, world!.

returns 27 or 26

00000000: 0a                                       .

returns 1 or 0

00000000: 6368 616c 6c65 6e67 650a                 challenge.

returns 10 or 9

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 21         Hello, world!

returns 13


returns 0

Sandbox:

  • Is this clear?
  • Is this a duplicate?
  • Other tags?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Does the extra rule mean that the input can have an optional trailing newline, or that the results in all of your test cases could be reduced by 1? If you mean the former I recommend adding a test case that doesn't end with a newline. If you mean the latter then I recommend explicitly saying the file will end with a newline character. Also I suppose this is a string challenge. Thanks again for using the sandbox :) \$\endgroup\$ – FryAmTheEggman Oct 3 '19 at 20:55
  • \$\begingroup\$ @FryAmTheEggman It means that all test cases could be reduced by one. This was intended as a code golf byte counter, and the newline most certainly isn't usually included. I'll clarify this and add another test case to highlight it. \$\endgroup\$ – gadzooks02 Oct 4 '19 at 15:17
  • \$\begingroup\$ So: discard all the input except the last line, and parse hex? Or just output the last line and claim that your output is in hex? IMO it would be a more interesting problem with xxd input, where the last line is not present. \$\endgroup\$ – Peter Taylor Oct 5 '19 at 9:00
  • \$\begingroup\$ @PeterTaylor If I were to switch to xxd, would that be a valid edit, or would that be too big a change such that I would have to post another challenge? \$\endgroup\$ – gadzooks02 Oct 5 '19 at 9:45
  • \$\begingroup\$ I'm sure far more significant edits have been made to sandboxed challenges in the past. \$\endgroup\$ – Peter Taylor Oct 5 '19 at 13:10
  • \$\begingroup\$ @PeterTaylor In that case, edited. \$\endgroup\$ – gadzooks02 Oct 5 '19 at 14:52
3
\$\begingroup\$

Java vs C++

Now posted at Time to settle this: Java vs C++

\$\endgroup\$
9
  • \$\begingroup\$ How vital is the validation to the challenge? \$\endgroup\$ – Unrelated String Aug 27 '19 at 21:01
  • \$\begingroup\$ @UnrelatedString I think it's fairly integral if the story is considered. Gotta inform the user that they're feeding you crap. Also it should add an extra element of challenge. \$\endgroup\$ – Mr Redstoner Aug 27 '19 at 21:07
  • 3
    \$\begingroup\$ @MrRedstoner Validation is generally considered tedious by the users of this site, rather than challenging. I'd recommend reconsidering - clearly the validation code could make use of the submissions as a subroutine. There are also a couple near dupes 1 2 but I haven't found a precise dupe. That said, thanks for using the sandbox! \$\endgroup\$ – FryAmTheEggman Aug 28 '19 at 0:36
  • 1
    \$\begingroup\$ getHTTP would result in... get_h_t_t_p? get_http? Error? Some other thing? \$\endgroup\$ – Chas Brown Aug 28 '19 at 1:42
  • \$\begingroup\$ @ChasBrown should be get_h_t_t_p, I shall add that. @FryAmTheEggman While I considered it part of the story, if those are the standards I figure I'll remove it and say the validation was done by a previous part of code. \$\endgroup\$ – Mr Redstoner Aug 28 '19 at 5:24
  • \$\begingroup\$ "If it is neither, output/return a falsey value." I would change this to something like "If it is neither, any unspecified behavior is fine (return a falsey value; give an error; try to convert it somehow anyway; etc.)." As mentioned by @FryAmTheEggman, validation is usually considered a distraction of the actual challenge (and can sometimes even double the code of the program/function for those answering), so most challenges assume the given input will always be valid. Apart from that the entire challenge looks fine, so +1 from me. Thanks for using the Sandbox! :) \$\endgroup\$ – Kevin Cruijssen Aug 28 '19 at 9:32
  • \$\begingroup\$ @KevinCruijssen Dang it missed that during the edit. Thanks for telling me! \$\endgroup\$ – Mr Redstoner Aug 28 '19 at 10:42
  • \$\begingroup\$ What should be returned from an input of a__b (two underscores)? \$\endgroup\$ – Value Ink Aug 29 '19 at 1:03
  • 1
    \$\begingroup\$ @ValueInk That would be invalid input. 'You may assume all input to be valid'. Therefore I refer you to the ANSI C standard for undefined behaviour. \$\endgroup\$ – Mr Redstoner Aug 29 '19 at 6:00
3
\$\begingroup\$

Can Jimmy escape the ghosts?

Posted: Can Jimmy escape the ghosts?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ S'all good, no problem \$\endgroup\$ – Veskah Oct 17 '19 at 14:05
3
\$\begingroup\$

Universal Self-correcting Program

The idea here is to make a program that can tolerate errors in its own code, while still functioning correctly.

Since "error" is too broad, we will define it by a single bit flip. Of course, more tolerant versions, that could accept swapping any character with any other character would still be valid.

This program is universal in the sense that you can write any other self-correcting program (with the same tolerance) -- more on that later.

Importantly:

1) This program takes as input a triple-redundancy string of characters, and outputs a corrected string.

2) This program executes correctly with any bit flip in its own code.

(1) Triple redundancy codes

A triple redundancy code consists of simply repeating each bit, character or byte 3 times. In this case we use characters.

Correction is done by taking the majority of the characters, so (A,A,B) is corrected to A, (A,B,B) is corrected to B and so on.

AAA => A
AAB => A
HHHEEELLXLLLXOO => HELLO

This is a very crude an inefficient code for correcting single bit errors, but it is the least complex, which is why I think may be the best choice here. Hamming codes are better but a little more complex.

(2) Error tolerance

Our program will be defined as error tolerant if it performs the desired decoding function for any single bit flip in its own code. It may take longer for some inputs or when some flips occur, but it should always terminate.

Putting it together

The error-tolerant program can receive as input a (possibly faulty) program, and outputs a error-free program. Therefore, if a single-bit error occurs anywhere in the system comprised of (decoder,input program), a corrected program will still be output.

Observation

I don't actually know if this is possible, quite possibly it won't be achievable in every language. If it is too hard, we may relax the tolerable errors.

Scoring

The score will reflect the reliability of your program to errors. Tolerance is simply the number of bit flips you code accepts anywhere. It must be at least 1 (accept 1 bit flip anywhere). Size is the length of your program in bytes.

The score is Score = Size / 2^Tolerance

Lowest score wins.

Note: Several other challenges are possibly solved by solving this one (which would make sense given its universality!) by hardcoding the input.

Detect if your program has been mutated

Write a program that always outputs “2012” - even if it's modified!

This solves the "Who Watches the Watchmen?" problem involved in error correcting programs, like in this challenge:

Meta radiation hardener

since the decoding program itself tolerates errors (what good would be an error correcting program that is itself in error? :p).

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Check the radiation-hardening tag for duplicates and rules clarifications, too. \$\endgroup\$ – AdmBorkBork Mar 7 '18 at 19:17
  • \$\begingroup\$ @AdmBorkBork Thanks, I wasn't aware of that. It appears no one has proposed a Universal radiation hardener yet (this is universal only in the sense of bit flip errors; those are actually a good model for radiation though!). \$\endgroup\$ – Real Mar 7 '18 at 19:30
  • 1
    \$\begingroup\$ Again Lenguage win lol \$\endgroup\$ – l4m2 Jan 8 '19 at 14:53
  • \$\begingroup\$ Even though your scoring involves code length you should use code-challenge instead of code-golf for challenges that are not solely scored by code length. \$\endgroup\$ – Laikoni Jan 10 '19 at 20:14
3
\$\begingroup\$

Golfing with 2s

It is well-known that all positive integers can be represented via a sum of powers of 2. For example, 13=2^3+2^2+2^0. We can rewrite the 3 and 0, to get 13=2^(2+2/2)+2^2+2^(2-2). A shorter representation might be 13=2^2^2-2-2/2, or a more repetitive one 13=2+2+2+2+2+2+2/2

Challenge

Your task is, given a nonnegative integer as input, output/return a string containing only 2s and elementary operations, which when evaluated will yield that integer. These operations are +, -, *, /, ^, and appropriate parentheses. Use of multiple consecutive 2s (22, 222, etc) is not allowed.

However, the string should tend to be one of the shorter representations of the integer in question. So for the above example with 13, 2^2^2-2-2/2 and 2^2^2-2/2-2 are the shortest representations.

The input can be in any convenient format, but the output must be in the above format, either to a file or STDIO.

Scoring

Short code and efficient representation are both prioritized, so the score is the length in bytes plus the average length of the returned string for 9, 57, 554, 1894, 25993, 113193, 2998225, and 52748566.

Rules

Standard loopholes not allowed

Standard input/output forms apply

Some degree of brute forcing is allowed, but the program must be able to handle each of the test cases in under a minute each.

Example outputs

0            2-2
1            2/2
2            2
3            2+2/2
4            2^2
5            2^2+2/2
6            2^2+2
7            2^2+2+2/2
8            2*2*2
9            2*2*2+2/2
10           2*2*2+2
57           2^(2^2+2)-2^2-2-2/2
554          2*2^(2*2*2)+2*2^2^2+2*2*2+2
1894         2*2^(2*2*2+2)-(2^2^2-2)*(2*2*2+2+2/2)
25993        (2*2^(2*2*2+2)-2*2^(2*2*2)-2^2-2-2/2)*(2^2^2+2/2)
113193       2*2^2^2^2-(2^(2*2*2+2)-2^(2^2+2)-2^2^2-2-2/2)*(2^2^2+2+2/2)
2998225      (2*2^2^2^2-(2^(2*2*2+2)-2*2*2-2-2/2)*(2*2*2+2+2/2))*(2^2^2+2*2*2+2/2)
52748566     (2*2^(2^2^2+2^2)-2^2^2^2-2*2^(2*2*2+2)-2*2^(2*2*2)-2^(2*2*2)-2*2*2-2/2)*(2^2^2-2-2/2)*2
\$\endgroup\$
10
  • \$\begingroup\$ It doesn't have to be optimal. It should tend to be optimal but you can trade it out for a much shorter program if it helps. \$\endgroup\$ – Exalted Toast Dec 8 '19 at 8:10
  • \$\begingroup\$ It might be a good idea to clarify length - do you mean the actual string length or the number of operations and 2s used? \$\endgroup\$ – FryAmTheEggman Dec 8 '19 at 20:19
  • \$\begingroup\$ Added clarification for both. To Fry, I mean the string length, but I'm not entirely sure what the difference is. \$\endgroup\$ – Exalted Toast Dec 9 '19 at 0:39
  • \$\begingroup\$ Can we use the numbers 22, 222, etc. in the output? \$\endgroup\$ – 79037662 Dec 10 '19 at 16:33
  • \$\begingroup\$ No. Will add clarification for that as well. \$\endgroup\$ – Exalted Toast Dec 12 '19 at 0:33
  • 1
    \$\begingroup\$ Can we submit a function that takes a value and returns a string? Typically you should try and avoid restricting input and output, and just rely on the community standards \$\endgroup\$ – Jo King Dec 13 '19 at 3:26
  • 1
    \$\begingroup\$ in reasonable time I know this is hard to specify, but as it stands it is too broad: what is meant by "reasonable time"? Some previous challenges say things like "it should run within a minute on a modern computer for inputs less than..." \$\endgroup\$ – Luis Mendo Dec 16 '19 at 9:47
  • \$\begingroup\$ Yeah, I'm not really sure how to specify it further. I only really added it because when I showed this challenge to my friend, they wrote a brute-force that goes through every string with those 8 characters and finds the shortest one, and it would take a few minutes for inputs > 30. Does being able to run each of the test cases in under a minute sound good? \$\endgroup\$ – Exalted Toast Dec 16 '19 at 19:15
  • \$\begingroup\$ That's the usual tactic, though you should probably specify what computer it is run on, since some will be faster than others. A possible idea could be the answerer has to run the biggest test case to completion, which should eliminate the worst of the brute force scripts \$\endgroup\$ – Jo King Dec 18 '19 at 7:33
  • \$\begingroup\$ Giving the integers you'll be testing with might allow people to optimise those specific inputs sneakily - maybe ask for a TryItOnline link and then give every answer a score yourself? Just a suggestion. \$\endgroup\$ – FlipTack Dec 27 '19 at 19:10
3
\$\begingroup\$

Eats, shoots and leaves

As you know, a panda eats shoots and leaves. Your task today is to write a panda in as few bytes as possible.

       1
      / \
     7   5
    / \   \
   2   6   9
      / \   \
     3   8   4

Here this tree has two branches, 1-7-6 and 1-5-9. The branch 1-7-6 has a shoot 2 and leaves 3 and 8, while the branch 1-5-9 has a leaf 4. After eating the shoots and leaves, your panda should output the following tree:

       1
      / \
     7   5
      \   \
       6   9

If your panda is a program or function, it must output the tree in the same format that you input it. Alternatively it can be a subroutine that modifies the tree in-place.

If it helps, you can assume that the tree has at least two nodes, and/or that each node has at most two child nodes.

No standard loopholes.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ What is a shoot, and what is a leaf? Is this question asked to remove all leaf nodes (nodes without children) in a tree? \$\endgroup\$ – tsh Jan 13 '20 at 1:30
  • \$\begingroup\$ @tsh For the purposes of the story, a shoot is a node which has no child nodes but whose parent has at least one grandchild node. Otherwise as you notice it has no effect on the outcome. \$\endgroup\$ – Neil Jan 13 '20 at 10:58
3
\$\begingroup\$

Bucket and Minimize

Post here

\$\endgroup\$
6
  • \$\begingroup\$ @FryAmTheEggman thanks for the info. updated \$\endgroup\$ – scrawl Jan 21 '20 at 9:40
  • \$\begingroup\$ "floor(12%5)+1 into 12 mod 5 buckets, and floor(12%5) in the rest". Shouldn't those floor(12%5) be floor(12/5) based on your \$\left\lfloor\frac{|L|}{N}\right\rfloor+1\$ formula? \$\endgroup\$ – Kevin Cruijssen Jan 22 '20 at 10:40
  • \$\begingroup\$ @KevinCruijssen er, yes. keeping things conventional. in my preferred language (k4) % is float division. i'll update it to avoid confusion. thanks! \$\endgroup\$ – scrawl Jan 22 '20 at 12:27
  • \$\begingroup\$ Ah ok. In most languages I know % is modulo and / is division. :) I thought maybe % was integer-division in your language of choice, making the floor obsolete. But your edit is indeed clearer. \$\endgroup\$ – Kevin Cruijssen Jan 22 '20 at 12:47
  • \$\begingroup\$ I would recommend cleaning the body of this answer and linking to the actual challenge: codegolf.stackexchange.com/q/198406/75323 \$\endgroup\$ – RGS Feb 2 '20 at 21:07
  • \$\begingroup\$ @RGS cleaned up \$\endgroup\$ – scrawl Feb 2 '20 at 23:55
3
\$\begingroup\$

Buildings made from cubes

Posted to main; thanks for input provided!

\$\endgroup\$
5
  • \$\begingroup\$ this looks perfect for fastest-code. with fastest-algorithm it's difficult to do complexity analysis on the solutions. \$\endgroup\$ – ngn Jan 4 '20 at 23:53
  • \$\begingroup\$ @ngn thanks, I’ve amended the alternative suggestion \$\endgroup\$ – Nick Kennedy Jan 5 '20 at 0:23
  • 3
    \$\begingroup\$ it may be good to mention explicitly that all blocks must form a single connected component, otherwise 2 separate 1x1x2 pieces would technically satisfy rules 1-4 \$\endgroup\$ – ngn Jan 5 '20 at 1:47
  • \$\begingroup\$ Is this basically \$a_n = \sum_{i=1}^n polyminoNumber(i)\cdot i^{n-i}\$? \$\endgroup\$ – the default. Feb 3 '20 at 14:56
  • \$\begingroup\$ @mypronounismonicareinstate no it's not, though it is related to the polyomino numbers. I've posted to main (sorry for not updating Sandbox post), so please see there for two implementations of code. \$\endgroup\$ – Nick Kennedy Feb 3 '20 at 17:35
3
\$\begingroup\$

Parse Iota

Iota is a simple programming language, considered the "sister" of the language Jot. More info can be found here Every Iota program consists of either an i, or a * followed by two Iota programs. In BNF, this is:

iota ::= i | *<iota><iota>

Challenge

Your task is to, given any input, output a truthy or falsy value based on whether or not it is a valid Iota program.

  • Your program may take input in any form agreed upon by the community here. It just has to be able to take input from the user in some form.
  • The same rule goes for output. See the post above for valid output methods. Output may be any truthy or falsy value in your language, including integers, strings, arrays, or objects. If it can be converted to a Boolean, it is OK.

Example I/O

Input: i
Output: 1
Input: hello
Output: 0
Input: *i*i*ii
Output: 1
Input: i*i
Output: 0
Input: ***
Output: 0
Input: *
Output: 0
Input: iiiiiiiii
Output: 0;
Input: i
Output: 1
Input: *ii
Output: 1
\$\endgroup\$
5
  • \$\begingroup\$ Suggested test cases: *, ***, iiiiiiiiiii \$\endgroup\$ – 79037662 Feb 12 '20 at 23:27
  • \$\begingroup\$ Ok, I added those @79037662 \$\endgroup\$ – sugarfi Feb 13 '20 at 0:37
  • \$\begingroup\$ I don't get how i*i*i*ii is produced. If I understand the grammar right, this is equivalent to checking if parens are matched after removing the final i that must come at the end, using *i as (). \$\endgroup\$ – xnor Feb 13 '20 at 7:12
  • \$\begingroup\$ @xnor - sorry, my bad. i fixed that. \$\endgroup\$ – sugarfi Feb 13 '20 at 12:02
  • 1
    \$\begingroup\$ I think that despite the different presentation, this would be similar enough to checking paren matching to be a duplicate. \$\endgroup\$ – xnor Feb 14 '20 at 11:22
3
\$\begingroup\$

The uniquely solvable sudoku

The task

Given a standard 9x9 sudoku board, output a Truthy value if that sudoku admits one and only one solution. Output a Falsy value if the sudoku has a number of solutions other than one. This means 0 solutions and two or more solutions.

The input

The board can be given in any sensible format. Some come to mind, and I'll exemplify for a 4x4 sudoku.

  • a 2D array with the state of the board, with any placeholder value for non-filled cells (including the digit 0, or no value at all if your language supports it): [[1,2,#,4],[#,4,1,2],[2,1,4,#],[4,#,2,1]]
  • a string of the digits row by row or column by column, so "12#4#412214#4#21" or "1#24241##14242#1"

The output

A Truthy value if the sudoku puzzle has a unique solution, Falsy otherwise.

Test cases

(To add)

Truthy

Falsy

\$\endgroup\$
2
  • \$\begingroup\$ Hmm, I'm surprised this isn't a duplicate with the amount of Sudoku-related challenges we have. Closest related challenge I could find is perhaps this one. \$\endgroup\$ – Kevin Cruijssen Feb 18 '20 at 16:21
  • \$\begingroup\$ @KevinCruijssen Thanks for your search! I can link this one, but this is still a new challenge, right? :) \$\endgroup\$ – RGS Feb 18 '20 at 17:44
3
\$\begingroup\$

Square Deltas

Given an strictly positive integer n, output all numbers in the sequence up to the index n. For the current test cases of the current challenge numbers are one-indexed. However, other formats are allowed as default.

Base sequence

We start from this sequence:

1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, ...

The sequence is described as follows: 1, 2 (xN), 1 repeated arbitary times. There are 2 more 2's than the previous 2-set, and the 2-sequence starts at 1. i.e.:

1,       2,       1,
1,    2, 2, 2,    1,
1, 2, 2, 2, 2, 2, 1,
and so on ...

However, our point is not to output this sequence. For every item in this sequence, add the item by that item of that sequence.

Adding the sequence

Here's an example of adding the sequence. Here, our sequence starts with 0:

  The sequence
    |
    v
0 + 1 = 1
1 + 2 = 3
3 + 1 = 4
4 + 1 = 5
...

Our generated sequence is therefore

0, 1, 3, 4, ...

Example test cases

Here is a sample program outputting the sequence up to the input.

3 -> [0, 1, 3]
10 -> [0, 1, 3, 4, 5, 7, 9, 11, 12, 13]

Sandbox

  • Can the challenge be clarified?
\$\endgroup\$
3
  • 5
    \$\begingroup\$ Why is the task asking for infinite output after index n, rather than a standard sequence challenge? A "standard sequence challenge" usually allows several I/O formats in a single challenge, including "input n -> the number at index n", "input n -> first n numbers", "no input -> infinite output of the sequence". \$\endgroup\$ – Bubbler Mar 6 '20 at 4:49
  • 2
    \$\begingroup\$ No, you don't need to make it harder. And even if it is too easy, please don't try to fake up the difficulty by enforcing unnatural I/O requirements. \$\endgroup\$ – Bubbler Mar 6 '20 at 4:56
  • 3
    \$\begingroup\$ Are you sure that you want to override the default sequence IO? Do you actually have a good reason for doing so? \$\endgroup\$ – Jo King Mar 12 '20 at 4:36
3
\$\begingroup\$

Pendulum Encoding

Given an array as an input (which can be any acceptable/convenient format in your language), implement pendulum encoding.

How do I do that?

The current iteration index starts at 0.

  • If the iteration index is even, append the current item onto the output list.
  • If the iteration index is odd, prepend the current item onto the output list.

An example

The input is [a b c d e f g].
Note that the letters a-g are atoms, to prevent confusion from the iteration index.
N: the iteration index

N:0 Out:      [a]
N:1 Out:    [b a]
N:2 Out:    [b a c]
N:3 Out:  [d b a c]
N:4 Out:  [d b a c e]
N:5 Out:[f d b a c e]
N:6 Out:[f d b a c e g]

The output should be [f d b a c e g].

Another example

The input is [u d l n u e m p].

N:0 Out:        [u]
N:1 Out:      [d u]
N:2 Out:      [d u l]
N:3 Out:    [n d u l]
N:4 Out:    [n d u l u]
N:5 Out:  [e n d u l u]
N:6 Out:  [e n d u l u m]
N:7 Out:[p e n d u l u m]

Test cases

Here's a sample program doing this encoding.

Take note that the atoms in the list aren't always unique.

[a,b,c,d,e,f,g]   -> [f,d,b,a,c,e,g]
[]                -> []
[a]               -> [a]
[a,b,c,d]         -> [d,b,a,c]
[a,b]             -> [b,a]
[a,b,d]           -> [b,a,d]
[a,b,a,c,b,c]     -> [c,c,b,a,a,b]
[a,a,b,b,c,c]     -> [c,b,a,a,b,c]
[u,d,l,n,u,e,m,p] -> [p,e,n,d,u,l,u,m]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I can't see any issues with this challenge apart from the usual "make sure that you specify that output and input can be taken in any reasonable and convenient format". \$\endgroup\$ – lyxal Mar 18 '20 at 0:00
  • \$\begingroup\$ The "example" in the first paragraph is confusing. It seems to be example input, but it deson't have clear context. If feels very out of place. \$\endgroup\$ – Wheat Wizard Mar 20 '20 at 15:16
  • \$\begingroup\$ Are the "atoms" unique? If not, you should at least include a test case where they aren't. \$\endgroup\$ – FryAmTheEggman Mar 20 '20 at 20:20
  • \$\begingroup\$ Naming a generic array a, then redefining a as a generic atom and never referring to the original array is not very helpful in an explanation. \$\endgroup\$ – Jonathan Frech Mar 21 '20 at 0:09
3
\$\begingroup\$

Join by intersection

Given a list of strings, output these strings joined by their largest intersecting parts. Your output has to be optimal. Strings have to be joined in the order given.

What is an intersection anyway?

Suppose you have two strings:

"abcbc" "bcbcd"

You extract all suffixes of the first string, as well as all prefixes of the second string:

["abcbc", "bcbc", "cbc", "bc", "c"]
["bcbcd", "bcbc", "bcb", "bc", "b"]

We trunctuate both of these lists to the length of the list of the smaller length (it's an identity in this current case).

Then, we find all items at the same index which are equal to the other item at the same index:

["bcbc", "bc"]
["bcbc", "bc"]

We return the longest string of the output. Therefore, the intersection is:

"bcbc"

How to join two strings by the intersection

To join by the intersection you simply

  1. Append the first string without the intersection to the output string
  2. Append the intersection to the output string
  3. Append the second string without the intersection to the output string

For example, in our example case:

"abcbc" "bcbcd"
(The intersection is "bcbc")

Step 1. Out:"a"
Step 2. Out:"abcbc"
Step 3. Out:"abcbcd"

Reducing a join over a list

If you want to reduce a join over a list

["abc","bcd","rfh","hal"]

You connect them by their longest common substring:

abc
 bcd
    rfh
      hal
=========
abcdrfhal

Therefore the expected output is abcdrfhal.

Further walkdown

You cannot join two strings if their substring can be found in the middle. For example:

["aXc","bXd"]

If you try to match them by the middle substring:

aXc
bXd

You would realize that the other overlapping characters are not equal to each other. That is, a is not equal to b, and c is not equal to d. In that case you simply append the string in the join:

aXc
   bXd
======
aXcbXd

Likewise, if either of these strings contain each other, but isn't equal to the other string, you should simply append the string. E.g.

["abcd","bc"]

would give

abcd
    bc
======
abcdbc

Substrings can overlap past each other. E.g.

["abc","bcd","cde"]

would result in the following join:

abc
 bcd
  cde
=====
abcde

which would evidently make the output abcde.


Strings have to overlap as much as possible. That means, in this example:

["abcbc","bcbcd"]

This is not okay (even if they do overlap):

abcbc
   bcbcd
========
abcbcbcd

Instead, this should be done:

abcbc
 bcbcd
======
abcbcd

The join is consecutive based on the consecutive inputs. For example:

abcde
  cde
     abcde
==========
abcdeabcde

Test cases

A program is worth a thousand words. Here 's a reference implementation that I use to check the test cases.

["abc","bcd","rfh","hal"] -> "abcdrfhal"
["mmm","qqq","rrr"] -> "mmmqqqrrr"
["abcbc","bcbcd"] -> "abcbcd"
["aXc","bXd"]    -> "aXcbXd"
["abc","bcd","cde"] -> "abcde"
["abcd","bc"] -> "abcdbc"
["abcde", "cde", "abcde"] -> "abcdeabcde"
\$\endgroup\$
15
  • \$\begingroup\$ How would you join aXc and bXd? They have the common substring X in the middle. \$\endgroup\$ – Bubbler Mar 25 '20 at 2:24
  • \$\begingroup\$ Can strings overlap past each other like abc,bcd,cde->abcde? \$\endgroup\$ – xnor Mar 25 '20 at 2:25
  • \$\begingroup\$ Do strings have to overlap as much as possible, or just overlap any amount? For example, for abcbc and bcbcd, is either of abcbcd or abcbcbcd OK? \$\endgroup\$ – xnor Mar 25 '20 at 4:43
  • \$\begingroup\$ Do strings have to be joined in the order given? I feel like the answer is surely "yes", but the text doesn't say outright. Really, I think all these Sandbox questions come from the fact that the task is never actually stated precisely, and doing that would probably head off any further question. \$\endgroup\$ – xnor Mar 25 '20 at 4:49
  • 2
    \$\begingroup\$ Along these lines, what happens if one string contains another? Do we do abcd,bc->abcd? \$\endgroup\$ – xnor Mar 25 '20 at 4:51
  • \$\begingroup\$ Suggested test case: abcde, cde, abcde. \$\endgroup\$ – Jonathan Frech Mar 25 '20 at 4:52
  • \$\begingroup\$ @JonathanFrech Well, what's the expected output? I thought it was abcde in this case. \$\endgroup\$ – user92069 Mar 25 '20 at 6:00
  • \$\begingroup\$ I was not completely sure what the output would be. abcdeabcde does seem reasonable. \$\endgroup\$ – Jonathan Frech Mar 25 '20 at 7:40
  • 2
    \$\begingroup\$ I still don't actually understand how the task works precisely. A reference implementation isn't a replacement for a specification. \$\endgroup\$ – xnor Mar 25 '20 at 23:09
  • \$\begingroup\$ @xnor I've added back the spec, can you understand it now? \$\endgroup\$ – user92069 Mar 26 '20 at 6:24
  • \$\begingroup\$ Not really, sorry. I still wouldn't know what abcd,bc would give. \$\endgroup\$ – xnor Mar 26 '20 at 6:29
  • \$\begingroup\$ @xnor Are there any more test cases you don't understand? \$\endgroup\$ – user92069 Mar 26 '20 at 6:35
  • \$\begingroup\$ This seems to be related to the shortest superstring problem for two strings, but you don't have to handle the case where one of the strings is a substring of another, and the joining order is fixed. Is that correct? Just informing that the specification spans four pages on my laptop, with default browser font size. \$\endgroup\$ – the default. Mar 26 '20 at 6:55
  • \$\begingroup\$ @a'_' en.wikipedia.org/wiki/… \$\endgroup\$ – the default. Mar 26 '20 at 6:58
  • \$\begingroup\$ @mypronounismonicareinstate Ah, it's a duplicate. Thank you for the mention. \$\endgroup\$ – user92069 Mar 26 '20 at 6:58
3
\$\begingroup\$

Sum in 2540 Sums

This is my attempt to pair with .

You need to write a program that sums all codepoints of the input string.

Rules

  • The input will always be in printable ASCII.
  • The sum of the codepoints of your source must be exactly 2540.

    • You are allowed to use your language's own code page to calculate your program's codepoints.
  • Null bytes (which don't contribute to your codepoint sum) are banned.

  • The program must not work with any consecutive substring removed.
  • This is . Your score is the length of your source code, the shorter being better.
\$\endgroup\$
6
  • \$\begingroup\$ You defined the "base score" only to reference that term exactly once. It seems to be move confusing than helpful. Wouldn't "The sum of the codepoints of your source must be exactly 2540" be clearer and shorter? \$\endgroup\$ – Wheat Wizard Apr 9 '20 at 21:18
  • \$\begingroup\$ Although I am neither suggesting nor recommending against, this could also work as code-bowling if you either outlaw null bytes or sum up the (codepoints+1). \$\endgroup\$ – Wheat Wizard Apr 9 '20 at 21:22
  • \$\begingroup\$ @AdHocGarfHunter The rules are a lot simpler if it were code-golf, and we haven't paired codepoint sum with code golf before. Also I need to fullfill a goal to pair code-bowling with code-golf. This analysis says that there are 11 tags not paired with code-golf, I'm going to make it 10. \$\endgroup\$ – user92069 Apr 9 '20 at 21:24
  • \$\begingroup\$ As far as I know, [pristine-programming] is the tag for programming with the substring removal restriction here. (I think this would work as a [code-bowling] as well as well) \$\endgroup\$ – the default. Apr 10 '20 at 0:12
  • \$\begingroup\$ @mypronounismonicareinstate So which side are you for? Code golf or code bowling? \$\endgroup\$ – user92069 Apr 10 '20 at 0:53
  • \$\begingroup\$ Probably code-golf. \$\endgroup\$ – the default. Apr 10 '20 at 1:07
3
\$\begingroup\$

Will this simplified befunge-93 program terminate?

The challenge today is to solve the halting problem for simplified befunge-93.

Simplified befunge-93 has exactly four instructions - > v < ^ @. The program is restricted to a 80x24 grid. Each of the commands modifies the instruction pointer (so that, for instance > makes the instruction pointer start executing commands to the right), except of the @ instruction, which terminates the program.

When the instruction pointer reaches the end, it wraps around (imagine the snake game).

You may read input in form of a string or a two-dimensional array using any reasonable device. The output may be either a truthy value if the program terminates, or a falsy value if the program doesn't terminate.

Example data

Input:
>v
^<

Output: Doesn't terminate.
----------------------------------------
Input:
> v
 @
^ <

Output: Doesn't terminate.
----------------------------------------
Input:
v@
[23 newlines]
>v

Output: Terminates.
----------------------------------------
Input:
v @
[23 newlines]
>v

Output: Doesn't terminate.
----------------------------------------
Input:

Output: Doesn't terminate.
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Possibly dupe? \$\endgroup\$ – null Apr 27 '20 at 8:47
  • \$\begingroup\$ is the instruction ptr initially at 0 0 and moving to the right? \$\endgroup\$ – ngn Apr 27 '20 at 8:55
  • \$\begingroup\$ yes, I maybe forgot to state that. But it's most probably a dupe right now, so I don't think I should push it forward anymore :P \$\endgroup\$ – Kamila Szewczyk Apr 27 '20 at 8:56
1
12 13
14
15 16
113

You must log in to answer this question.

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