535
\$\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

3497 Answers 3497

1
100 101
102
103 104
117
0
\$\begingroup\$

Text in aLtErNaTiNg cApS

Sometimes, we want to convey sarcasm in a text message or in a YouTube/Reddit comment. To this end, "alternating caps" is often used. Your task, should you wish to accept it, is to write code that turns the input text into its "alternating caps" version.

(This is a deleted rule. You should ignore this for the challenge) For most sans-serif web fonts, it is hard to distinguish capital I (for India) and lower-case l (for Lima). So we want to avoid either of these letters in our output. To achieve this, we are allowed to sacrifice "exact alternating-ness" of the output. Details below.

Input:

  1. A string of words involving [a-zA-Z], with one space in between each word.
  2. You may not assume whether or not the string ends with a space/newline/etc.

Output:

  1. The input, turned into "alternating caps form", with the first letter of each word being lower-case.
  2. (Deleted; you should not implement it. I have included it just to illustrate my thought process) You may not output any capital I (I, for India) or lower-case l (l, for Lima). To avoid these, you may continue outputting the same letter-case as the previous letter, but you must switch the letter-case at the earliest possible instance. (note to self: this requirement means there are sometimes more than two letters of the same case, which I don't really want)

  3. Non-suppressible output can be ignored.

Rules:

  1. Standard loopholes are forbidden.
  2. You must take input from and output to natural places, according to your language.
  3. This is code-golf, so the lowest byte-count wins. Ties are broken by earliest submission.
  4. Please provide a way for readers to test your code (e.g. TIO).
  5. An ungolfed version and an explanation for your code is appreciated, although not required for the challenge.

Examples

Input -> Output
---------------
alternating -> aLtErNaTiNg
lower case letters -> lOwEr cAsE lEtTeRs

Examples that follow the deleted rule (which you should not implement -- these are just for your interest:

I used dcode to find some of these examples. holding -> hOLdiNg radii -> rAdii (has more than 2 lower-cases in a row, if using my rules) fall -> fALL (has more than 2 capitals in a row, if using my rules) volleyball -> [even if you are allowed to change the previous letter-cases to try to stop 'ALL' (3 capitals in a row) from appearing, there is a non-unique way of doing so]

Good luck!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Unfortunately this has been posted before: codegolf.stackexchange.com/q/122783 \$\endgroup\$
    – pxeger
    Apr 8 at 8:36
  • \$\begingroup\$ @pxeger That challenge is slightly different, as this one asks for alternating characters rather than alternating letters. lower case letters in that challenge would become LoWeR cAsE lEtTeRs (or lOwEr CaSe LeTtErS), neither of which are acceptable outputs for this \$\endgroup\$ Apr 11 at 14:02
0
\$\begingroup\$

Take two registers, zero-extend one to another one on x64 in a single instruction.

Here, registers are r0-r15(64-bit), r0d-r15d(32-bit), r0w-r15w(16-bit) and r0b-r15b(8-bit), where regs marking same number share same lowest part. In case there's no solution (e.g. writing into r0d, which the opcode would behave writing to r0), output something obviously not an opcode.

Opcodes:

90              do nothing
89 11sssddd     move 16/32/64-bit[1] from sss[2] to ddd[2]
88 11sssddd     move 8-bit from sss[2] to ddd[2]
0F B7 11dddsss  move from 16-bit sss[2] to 32/64-bit[1] ddd[2]
0F B6 11dddsss  move from 8-bit sss[2] to 16/32/64-bit[1] ddd[2]
101101dd 00     move from 8-bit 0dd[2] to 16-bit 0dd[2]             
[WIP]

Shortest code win. -35 Bytes if you support ax cx dx bx sp bi sp di aliasing r0w-r7w, and rax-rdi as r0-r7, eax-edi as r0d-r7d; - another 35 Bytes if you support al cl dl bl aliasing r0b-r3b and ah ch dh bh as theoretically r4b-r7b but without REXs.

\$\endgroup\$
0
\$\begingroup\$

Make an image with the pixels from another (WIP)


Given a target image and a source image, output an image that resembles the target image by rearranging the pixels of the source image.

You will be scored based on speed and accuracy.

$$ score = {similarity(Image_{target}, Image_{result}) \times {time_{reference} \over time_{program}}} $$

Higher scores are better

\$\endgroup\$
0
\$\begingroup\$

On a 150x150 area, each cell have 15% probable of being a mine. Opening a safe(non-mine) cell tells you amount of mines with <1.5 distance. Opening a mine makes you fail. Find most safe cells in 5 second.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ This isn't very well specified. How will the grid be given, and will it be given via interactive I/O or do we need to provide a function that will be called multiple times? How will this be timed? Will testing be done via a fixed sample? Also, I am pretty sure that any reasonable implementation (doesn't even need extreme optimizations) will be able to clear an entire 150x150 board in well under 5 seconds. \$\endgroup\$
    – hyper-neutrino Mod
    Apr 10 at 17:22
  • \$\begingroup\$ @hyper-neutrino What about 1500x1500? Giving grid method quite flexible \$\endgroup\$
    – l4m2
    Apr 10 at 18:13
0
\$\begingroup\$

Packing numbers to interval

,

Interval notation is a way to write complicated range bounds more conveniently and concisely than writing an inequality.

Like a list 1, 2, 3, 4 can be written like [1,4].

There have been already challenges on interpreting interval notations to number ranges, but now we will do the reverse.

Some examples (test cases):

  • Input will be a list of numbers (can be positive, negative, 0, but not fractions)

  • Input list can be unsorted

  • If there is gap between the numbers (I mean in a list like 1,2,5,6, 3,4 is missing), you have to write multiple intervals seperate by Union sign (U)

  • There will be no leading 0s in input numbers

  • If there is only one number seperate in an interval (I mean like 2 in the list of 2,5,6,7) then make a seperate interval (for the example [2]U[5,7]

  • The intervals should go from smallest to largest (for example 1 2 5 6, [1,2]U[5,6] is valid but [5,6]U[1,2] not.

  • Input numbers can be separated by anything, it is up to you.

1 2 3 4 -> [1,4]
5 3 4 1 2 -> [1,5]
2 1 6 5 -> [1,2]U[5,6]
6 7 9 8 -4 -2 -3 0 2 1 -> [-2,-4]U[-0,2]U[6,9]

Standard loopholes apply, shortest code wins.

\$\endgroup\$
2
  • \$\begingroup\$ Could this be a duplicate of this? \$\endgroup\$
    – Leo
    Apr 12 at 3:47
  • \$\begingroup\$ @Leo hmmm... i think its really a duplicate \$\endgroup\$
    – wasif
    Apr 12 at 3:56
0
\$\begingroup\$

Two player tic-tac-toe game

Create a Tic-Tac-Toe game that allows two human players to play against each other.

  • The drawn board can be either in ASCII or graphical (You can use 1-9 digits as a place holder in tic tac toe board)
  • Program should randomly choose whose turn is first and randomly give two players X or O
  • let both users know whose turn it is amd prompt for input
  • Check for winning, and when one player is won, let them both know about win (same for draw game)
  • Enforce all tic-tac-toe rules

Standard loopholes apply, shortest code wins

\$\endgroup\$
0
\$\begingroup\$

Hamming Distance Lookup Extravaganza

Note: I was originally just going to post this, but I was having trouble coming up with a good scoring strategy. I'd like to make sure that the instructions are clear and scoring strategy is fair and works. Thanks!

Note: This question is a WIP, and some parts may be incomplete or in the middle of editing!

Story

Bitty Benny runs a clothing factory, where, among other things, he produces bundles of shirts. Each shirt has a tag (don't worry, it's not itchy) describing what type of shirt it is.

Similar shirts have similar tags, and Bitty Benny wants to create an organization system, that, given a tag, will fetch the shirt with the most similar tag. Each tag is the same length, and lists a series of ones and zeros. To compare how similar tags are, Bitty Benny bought a Hamming Shirt Comparator (Mark II). Here's a loose schematic as to how the comparator works:

  1. First, the Comparator takes the two tags and lays them side by side, like so:
    +----------+
    | 10010100 |
    +----------+
    | 00101101 |
    +----------+
    
  2. Then, the comparator goes through each pair of numbers and counts the number of differences:
    +----------+
    | 10000100 |
    +-|---|--|-+
    | 00001101 |
    +-|---|--|-+
      x   x  x : 3 differences
    
  3. The comparator then laser-engraves the difference onto a marble stone tablet. Some argue that the Mark I was better, because it printed out results instead, but Bitty Benny likes the satisfying thunk of the tablet as it falls from the machine.

The lower the number the comparator outputs, the more similar the shirts are. A perfect match has a score of 0, an imperfect one has a score of the length of the tag.

Bitty Benny has a lot of impatient (but well-paying) clients who demand specific types of shirts. How can Bitty Benny organize and search through the shirts to find the closest-matching tag as quickly as possible?

Formal Definition

A tag is a bit-vector of size N, where N is a power of two. For this particular challenge we'll assume N to be 64.

Hint: On modern CPU architectures, a tag can be represented by a word (an unsigned 64-bit integer), and the difference between two tags can be written as an xor then a popcount (count the number of ones in the binary representation of the integer). This distance is generally referred to as the hamming Distance (lowercase 'h', of course) between two words.

Naïvely, using a linear search, finding a tag will take O(n) time. Faster solutions exist - can you find them?

Input

Your program will take two inputs:

  1. A list of random tags.
  2. a different list of target tags.

These lists may be of different sizes. The input format will be as follows:

<Size of random tags list>
<tag as a decimal number `0 <= n < 2^64`>
...
<Size of random target tags list>
<tag as a decimal number>
...

The competition input has been generated, and can be found here.

Task

For each target tag, determine the closest match in the random tag list, using hamming Distance as described above.

In the case of a tie, i.e. multiple tags have the same minimum distance, any one is valid.

Output

In the order of reading, print out the closest match of each tag as a number, in the appropriate base.

Scoring and Rules

The goals of this competition are to find solutions that are:

  1. Fast, in terms of execution time.
  2. Clever, in terms of algorithm used, amortized cost, and write-up.

To score your program:

Note: I have to finish writing example baseline program Note: I have to generate and upload the testing list. Ideally it should be big enough that the naive solution takes around 3 seconds on a modern computer.

  1. Translate this naïve idiomatic program from Rust to your language of choice.
  2. Time the naïve solution in your language of choice.
  3. Write an optimized solution in the same language, and time it using the same technique.
  4. Your score is the optimized execution time, in seconds + that times the speedup, lower scores are better:
    score = fast_time +  ((fast_time ** 2) / slow_time)
    

Time your programs using time, include the time taken for I/O.

Note: This scoring method is good for two reasons:

  1. In the case that there is no speedup compared to the baseline, the score is just 2x the time.
  2. Any speedups over the base version will decrease the score, but the score will never be less than the wall-clock time it takes.

To determine the answer with the best writeup, we'll also be running a popularity contest.

Entry Template

I'm no stickler, but here's a loose entry template if you'd like to keep things consistent:

## <Language> <Speed Score> (<Calculation>)
<Link to idiomatic solution>
```
<Optimized entry>
<If over a respectable size, put a link here instead>
```

## How it works
<breakdown of the code>
<and the method used>
<and any other interesting notes>

Good luck, and happy tagging! Bitty Benny awaits your entry!

\$\endgroup\$
0
\$\begingroup\$

Participant number

,

A math Olympiad will be held, and participants are being registered. The highest number of participants is 100. Each participant is given an ID number. It is given in a sequence like \$100, 97, 94, 91, 88, ...., 1\$, and when the first sequence is over, then \$99, 96, 93, 90, 87, ...., 3\$ sequence and so on.

Let's assume one of the participant's ID number is \$k\$ and he/she is the \$n^{th}\$ participant. Given the value of \$k\$, return the value of \$n\$.

Test Cases

59 -> 81
89 -> 71
16 -> 29
26 -> 92
63 -> 47
26 -> 92
45 -> 53
91 -> 4
18 -> 62
19 -> 28

There will be no leading zero in input. Standard loopholes apply, shortest code wins. In output there can be trailing whitespace.

\$\endgroup\$
1
0
\$\begingroup\$

Given a table(2D array of strings), arrange width of each column to shorten total width, such that containment in each cell can be fully shown with a space after it, being allowed to occupy next several cells if they are empty. In another word, for each column provide a width \$W_j\$, making \$\sum_jW_j\$ smallest, and for each non-empty cell in column \$i\$ , if there're \$k\$ empty cells on adjacent right, then its length is smaller than \$\sum_{j=i}^{i+k}W_j\$.

Samples:

"1234", ""  => [2,3] "1234 
"a"   , "b"           a b  "

"Date"  , ""  , "Sum"            "Date   Sum
"Mar"   , "1" , "220"             Mar 1  220
"Mar"   , "15", "130" => [4,3,4]  Mar 15 130
"Apr"   , "3" , "100"             Apr 3  100
"Sum_Up", ""  , "450"             Sum_Up 450 "

"aaa" ""    ""               "aaa
""    "bbb" ""    => [0,0,4]  bbb
""    ""    "ccc"             ccc"
\$\endgroup\$
0
\$\begingroup\$

Fastest unique finder

\$\endgroup\$
0
\$\begingroup\$

Given a string s, find a string t, containing only printable ASCII characters (32-126), such that PPCG53675(t)=s. You can assume such string exist.

Examples:

  • tmop => test (and 23 other possible outputs)
  • TEST => T5oV (and 23 other possible outputs)
  • !!!! => !!!! (and 17)
  • !! => ! (only one solution)
  • ~}}~ => ~|~~ (only one solution)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ @RedwolfPrograms How? ac is not a valid output for ac \$\endgroup\$
    – l4m2
    Apr 13 at 18:35
  • \$\begingroup\$ Oh, didn't notice that it can be multiple characters. \$\endgroup\$ Apr 13 at 18:38
  • 3
    \$\begingroup\$ It might be harder than it sounds (at least to solve efficiently), as there are edge cases involving values close to 32 and 126. Looks like a good challenge, though it needs some good test cases. Also needs a self-contained description. \$\endgroup\$
    – Bubbler
    Apr 15 at 9:11
0
\$\begingroup\$

Non-Hamming numbers

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I would suggest including a definition of hamming (or non-hamming) numbers in the challenge description. \$\endgroup\$
    – Delfad0r
    Apr 11 at 10:10
  • 3
    \$\begingroup\$ You definitely need to define non-hamming numbers - challenges should never require you to look at an outside source (the challenge you linked should too), and I would suggest providing a detailed example of how to compute them as well. Also, add the sequence tag. \$\endgroup\$
    – pxeger
    Apr 11 at 10:25
0
\$\begingroup\$

Brainfuck to ESOPUNKS

Brainfuck use 8 instructions

byte(or bigint, your choose) a[inf]; bigint i;
+  ++a[i];
-  --a[i];
,  a[i]=getchar();
.  putchar(a[i]);
[  while(a[i]){
]  }
<  if(--i<0) undefined_behavior();
>  ++i;

ESOPUNKS have two registers X and T, two I/O ports #STDI(stdin, read like how brainfuck does), and #STDO(stdout, undefined behavior if written <0 or >255), use these instructions:

COPY a b     b=a; a,b,c can be X,T,#STDI,#STDO or integer as long as it makes sense(no giving integer a value, etc.)
ADDI a b c   c=b+a;
SUBI a b c   c=b-a;
MULI a b c   c=b*a;
DIVI a b c   c=b/a; Halt if a=0
MODI a b c   c=b%a; Halt if a=0
MARK label   label:
JUMP label   goto label;
TJMP label   if(T) goto label;
FJMP label   if(!T) goto label;
TEST a op b  T = (a op b); op = <, =(==), >
HALT         exit(0)

(Didn't cover all instructions from esolangs as some are not implemented in the interperter)

Now write a program that converts a Brainfuck program into a ESOPUNKS one. Your ESOPUNKS output should have O(1) lines.

Note:

  • It's possible to convert. Wiki shows a proof that applies with small removal.
  • It's possible for bounded lines to store unbounded info as unbounded integer behave as operator
  • Outputting may need a snippet repeating 256 times to allow any possible output; However I don't care length of output(as long as it's bounded), and the repeating can be generated with small code, so this shouldn't matter much.

Code-golf, shortest code in the language wins.

\$\endgroup\$
1
  • \$\begingroup\$ Unless I'm misunderstanding some aspect, this is unreasonably hard. Converting between a TM (brainfuck) and a 2 counter machine (Esopunks), while possible, has a lot of caveats that are delineated by the wiki page you linked, most relevantly that the input has to be given as an initialization of one of the counters as an integer encoding a TM. Then the actual conversion algorithm between TM and 2CM is also extremely involved, not least of which includes encoding 4 counters in one via the prime factorization \$2^a3^b5^c7^d\$. This is closer to a thesis project than a code golf... \$\endgroup\$
    – kops
    Apr 27 at 1:28
0
\$\begingroup\$

Extract json, with only few bytes.

Extract the "name" of each dictionary in the json list.

You are allowed to use any package which can be installed on Ubuntu 20.04.

Example json:

[
    {
        "id":"d963984c-1075-4d25-8cd0-eae9a7e2d130",
    "extra": {
        "foo": false,
        "bar": null
    },
    "created_at":"2020-05-06T15:31:59Z",
    "name": "NAME1"
    },
    {
    "id":"ee63984c-1075-4d25-8cd0-eae9a7e2d1xx",
    "name": "NAME2"
    }
    ]

This script would work:

import json
import sys

for item in json.loads(sys.stdin.read()):
    print(item['name'])

Desired output:

NAME1
NAME2

But since I am very lazy, I am looking for a solution which needs less characters.

The solution with the minimal number of bytes wins.

Using non-ascii characters is not allowed.

Compressing into base64 or similar is not allowed. The solution should be "type-able" by a human.


Since the question does not fit ot code-gold, I published it here: https://stackoverflow.com/questions/67194693/filter-json-on-the-command-line

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Welcome to the site, and thank you for using the sandbox. Note that, by default, we count code in number of bytes, not number of characters, to prevent abuse like compressing code into Unicode characters that might need up to 4 bytes each. \$\endgroup\$
    – Adám
    Apr 20 at 9:45
  • \$\begingroup\$ @Adám I updated the question. It should be type-able. Do you think it is ok now? \$\endgroup\$
    – guettli
    Apr 20 at 9:51
  • 1
    \$\begingroup\$ Why prohibit non-ascii characters? I can certainly type non-ascii characters on my keyboard, and I'm human. \$\endgroup\$
    – Adám
    Apr 20 at 9:53
  • 1
    \$\begingroup\$ Why prohibit compression? If that gives me a better score, then why not use that? \$\endgroup\$
    – Adám
    Apr 20 at 9:53
  • 1
    \$\begingroup\$ I'd use the word "extract" rather than "filter", since we're not reducing the number of dictionaries. Rather, we're extracting the "name" member of each. \$\endgroup\$
    – Adám
    Apr 20 at 9:55
  • \$\begingroup\$ @Adám I search for a solution which I could easily apply in the future again. I need to extract data from json from time to time and I am searching for a pattern which I can re-use. That's why compression (like gzip/base64/...) makes no sense to me. I want the solution to be readable and more or less easy to understand. Maybe "bytes" is the wrong unit for what I want. \$\endgroup\$
    – guettli
    Apr 20 at 19:25
  • 2
    \$\begingroup\$ I think your challenge is interesting and has potential, but please do not try to use this site as a place to get programming help. For that, try Stack Overflow instead. Be warned that people here will break all best practices and accept extreme inefficiency to save a single byte. If you try to circumvent this culture (which is the purpose of the site!) then you will be met with what can be perceived as hostility. \$\endgroup\$
    – Adám
    Apr 20 at 19:54
  • \$\begingroup\$ Even though you've posted on SE, do you want to sort this out as a proper code golf challenge for this site too? \$\endgroup\$
    – Adám
    Apr 21 at 11:53
0
\$\begingroup\$

Largest Compatible Maze

\$\endgroup\$
0
\$\begingroup\$

Generate a uncomputable number

An uncomputable number is a number that some digit can't be computed in finite time.

Now you're to generate and output one of them.

You can(and need to) use \b to undo an outputted byte, but every byte should stop changing from some time.

An example solution, assuming stepN(p, n) checks if program p halts in n steps, returning 0 or 1:

s = [];
output('0.');
for (i=1; ; ++i) {
    t = [stepN(j, i) for j in [1,n]]
    while (s is not a prefix of t) {
        output('\b');
        s.remove_last();
    }
    for (j=s.length; j<t.length; ++j) {
        s.insert_to_last(t[j]);
        output(t[j]);
    }
} // 0.s[0]s[1]s[2]s[3]..., s[i] mean if program i halt

Shortest code wins.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Where does your definition of "uncomputable number" come from? What I'm familiar with is "a number defined in terms of uncomputably fast-growing function". \$\endgroup\$
    – Bubbler
    Apr 22 at 9:07
  • \$\begingroup\$ I can imagine that a slight modification of the challenge would work using my definition: Pick an uncomputable function f(n). Given n as input, output an infinite sequence of numbers, which should eventually produce an infinite stream of f(n) and nothing else. A possible answer in this case is a BF busy-beaver function, where you run each step of all syntactically valid BF programs of length n and update the answer whenever one of them halts. \$\endgroup\$
    – Bubbler
    Apr 22 at 9:13
  • \$\begingroup\$ @Bubbler Defined as "not computable" \$\endgroup\$
    – l4m2
    Apr 22 at 9:51
  • \$\begingroup\$ Then I guess you should include in the first sentence that you want a real number, as opposed to an integer. I could find only one uncomputable real number, Chaitin's constant, which is a halting probability of a random program (in a hypothetical programming language with a specific property). Also, IMHO erasing digits with \b is superfluous and unnecessary, and you should allow outputting infinite stream of digit strings (and allow printing or returning them). \$\endgroup\$
    – Bubbler
    Apr 22 at 10:14
  • \$\begingroup\$ Also, should the number be output in decimal, or can I output it in binary or other base? \$\endgroup\$
    – Bubbler
    Apr 22 at 10:21
  • \$\begingroup\$ @Bubbler If an expressing is uncomputable in binary, it is for decimal \$\endgroup\$
    – l4m2
    Apr 22 at 10:22
  • \$\begingroup\$ @Bubbler If you don't use \b then it's not uncomputable \$\endgroup\$
    – l4m2
    Apr 22 at 10:24
  • \$\begingroup\$ I mean, if I want to revise an earlier digit, I can print a new number instead of overwriting the number. \$\endgroup\$
    – Bubbler
    Apr 22 at 10:30
  • \$\begingroup\$ @Bubbler You mean the output method of this? \$\endgroup\$
    – l4m2
    Apr 22 at 15:32
  • \$\begingroup\$ Yes, something like that \$\endgroup\$
    – Bubbler
    Apr 22 at 21:46
0
\$\begingroup\$

Write a fast-growing assembly function

Synopsis

Your goal is to implement the (asymptotically) fastest growing function within bounded code on a fictional CPU utilizing a quite limited, yet (probably) turing-complete instruction set.

Environment

The CPU utilizes unbounded RAM as well as two registers, the accumulator A and the program counter C, with words consisting of arbitrary integers, such that neither overflows nor underflows are possible. RAM is used to store data as well as code, allowing for self-modifying programs. Each instruction takes one parameter and therefore consists of two words; all instructions of your program are stored sequentially in RAM, starting at address 0. The following instructions can be used, P representing the parameter of the instruction:

Mnemonic Corresponding word Behavior
LOAD P 0 A := RAM[P]; C += 2
SAVE P 1 RAM[P] := A; C += 2
CNST P 2 A := P; C += 2
ADDT P 3 A += RAM[P]; C += 2
NEGA P 4 A := -RAM[P]; C += 2
JUMP P 5 C := P
JMPN P 6 If A <= 0 then C := P else C += 2.
HALT P every other number The program halts.

At each step, the instruction at address C will be executed using the parameter stored at C + 1. Both A and C will be initialized to 0 at the start of a program's execution. The word at -1 is supposed to be your input which can be guaranteed to be non-negative, other words not storing any instructions initially contain 0. The number stored at -2 will be considered your program's output, which must also be positive in all but finitely many cases.

Rules

At the initial state, your program may not occupy more than the first 2048 words, however, during execution, there are no bounds. Of course, you don't have to write your program in bytecode, using some assembly equivalent or ultimately any other language is fine as well, as long as you provide some rules/translator and show the result does not exceed the given bounds.

Every answer should come with some rough argument showing the program always halts, as well as some approximate lower bound on its growth rate. As the given space might very well suffice for some extremely fast-growing functions, it might be helpful to utilize the slow-/fast-growing hierarchy, as it provides a relatively simple way to compare two answers. Answers will be ranked by lower bounds that can be shown to hold.

Questions

I wonder what tags could be used in this case, atomic-code-golf, restricted-source and busy-beaver perhaps? Not entirely sure whether these fit. Also, is there any behavior left undefined? It doesn't seem like that's the case, but there might be some edge cases I forgot about.

\$\endgroup\$
7
  • \$\begingroup\$ 2048 words should be enough to run every possible program \$\endgroup\$
    – l4m2
    Apr 23 at 10:35
  • \$\begingroup\$ @l4m2 what do you mean by that? you surely can't just take the first <input> programs and run them, otherwise you'd have to solve the halting problem \$\endgroup\$
    – univalence
    Apr 23 at 12:01
  • \$\begingroup\$ I mean there's, in any measure, way to make it better, in the 2048, and we don't want a "who say bigger number" game \$\endgroup\$
    – l4m2
    Apr 23 at 15:39
  • \$\begingroup\$ @l4m2 Ah, so you'd reduce the maximum size, correct? \$\endgroup\$
    – univalence
    Apr 23 at 16:13
  • \$\begingroup\$ no, reducing to turing incomplete likely make it too weak \$\endgroup\$
    – l4m2
    Apr 23 at 16:44
  • \$\begingroup\$ @l4m2 not the RAM size, the allowed code length \$\endgroup\$
    – univalence
    Apr 23 at 16:57
  • \$\begingroup\$ since this has been posted, it suggest shortening to one line and deleting to save sandbox space. \$\endgroup\$
    – Razetime
    Apr 30 at 2:51
0
\$\begingroup\$

May the wind be always at your back

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Challenge is well-written with good test cases. My only critique is that as a puzzle, it's just "is there a path from A to B in this directed graph?" But to get the directed graph you have to parse a bunch of ascii (well, unless you are very flexible with input), which is a "turn this ascii into a directed graph" challenge. The former challenge would likely be a duplicate. The latter is somewhat interesting, but perhaps a bit mechanical. I find it helpful to look at challenges from this "what is the heart of this problem?" perspective. \$\endgroup\$
    – Jonah
    Apr 25 at 0:48
  • 1
    \$\begingroup\$ Note: The above isn't to say you shouldn't post the challenge -- it's definitely postable quality. Just giving you some feedback. \$\endgroup\$
    – Jonah
    Apr 25 at 0:50
  • \$\begingroup\$ Thanks for the feedback, though I'm not sure how to improve this (the only thing I can think of is to make the challenge be "list all of the possible paths"). Do you have any suggestions? \$\endgroup\$
    – knosmos
    Apr 25 at 1:13
  • \$\begingroup\$ You could make it "turn this ascii into an adjacency list or matrix," which is more focused, but becomes too technical. My comment is probably more useful for evaluating future ideas rather than as a way to improve this one. \$\endgroup\$
    – Jonah
    Apr 25 at 1:16
  • \$\begingroup\$ Okay, thank you! \$\endgroup\$
    – knosmos
    Apr 25 at 1:17
  • \$\begingroup\$ I'd suggest adding in a falsey testcase where the wind deposits you on a patch of calm sea next to Ithica, similar to the west path in the third test case \$\endgroup\$ Apr 25 at 13:04
  • \$\begingroup\$ Thanks, implemented \$\endgroup\$
    – knosmos
    Apr 25 at 14:27
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ Apr 25 at 17:28
0
\$\begingroup\$

Compute a real root of a cubic polynomial.

You are given a cubic polynomial of the form \$x^3 + a x^2 + b x + c\$ and your task is to compute one real root of this polynomial, or equivalently a solution to the equation \$x^3 + a x^2 + b x + c = 0\$.

Input will be three numbers \$a\$, \$b\$ and \$c\$. These are guaranteed to be real numbers. The inputs may be taken separately or as a list or a vector or whatever else is convenient in your language.

A cubic polynomial always has at least one real root, and can have up to three. It always has three complex roots but the non real ones are of no interest for this challenge. If the polynomial has multiple real roots, outputting any one of them is fine.

Output should be one number. Solutions with three correct decimal places are good enough, more accuracy or exact algebraic expressions are fine too.

This can be solved by using Cardano's formula but this requires handling of complex roots and some messy lengthy algebra. Alternatively one could use some algorithm for a numeric approximation such as Newton's method. If your language has a build-in that works as well as long as you fish out exactly one real root.

Test cases can be easily generated with any online solver for cubic equations such as this one.

This is , so the shortest code in bytes wins.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and thank you for using the Sandbox! I've edited the MathJax slightly (we use \$ as delimiters here), and added in a couple more edits to fit the site defaults slightly better. Feel free to revert these if you dislike them. I'd suggest including some test cases in the challenge body as challenges should be self-contained, and linking to the generator for even more. Finally, for tags, I'd suggest [code-golf], [polynomials], [math] and [number-theory] \$\endgroup\$ Apr 26 at 19:14
0
\$\begingroup\$

Your client asks you to produce an "org chart" of their statically generated Website's navigation paths.

You can use the Google sheets chart feature if you like, as long as the chart looks similar to what the client expects here:

Notice that a child can only have one parent, so you need to calculate the shortest path to the root element (aka "Home").

Your coding challenge is to create the same chart programatically for the static html as well as their Website at https://simple.goserverless.sg/

Example output:

generate-site-structure [index.html | https://simple.goserverless.sg/]
Bread,Products
Jam,Products
Products,Home
Privacy Policy,About Us
Sustainability statement,About Us
About Us,Home
\$\endgroup\$
5
  • \$\begingroup\$ Welcome to the Sandbox! This currently isn't nearly clear enough, I'd recommend looking at some other graphical-output challenges to see the typical requirements. You also haven't specified an objective winning criterion; the most popular by far is code-golf (shortest code), but there are also some others like fastest-algorithm or test-battery. \$\endgroup\$ Apr 29 at 2:55
  • \$\begingroup\$ Thanks, I've tried to be clearer by stating what the expected output is to be. Does that make sense? \$\endgroup\$
    – hendry
    Apr 29 at 6:12
  • \$\begingroup\$ I'm not sure I understand the goal. Are programs supposed to print that exact text, or a graphical representation of it, or take some sort of site as input and make a representation of it? \$\endgroup\$ Apr 29 at 6:21
  • \$\begingroup\$ The output is the text/csv which can be drawn by Google Sheets as a organizational chart. \$\endgroup\$
    – hendry
    Apr 29 at 7:38
  • 1
    \$\begingroup\$ That definitely needs to be much clearer in the post. Without much prior knowledge or assumptions, it should be possible to tell exactly what is expected of answers from the challenge text, and also typically with a bit of explanation on how and some test cases. I'd recommend answering a challenge or two, doing that gives you a pretty good idea of what a challenge needs in order to be clear enough to answer. \$\endgroup\$ Apr 29 at 13:25
0
\$\begingroup\$

[Draft] 2x2 algorithm with half the faces

A fun fact about the 2x2x2 Rubik's cube is that due to the way a 2x2 only has two layers, doing one turn on one face is indistinguishable from doing the same direction turn on the opposite face and then rotating the cube. So algorithms, that is sequences of moves and cube rotations, ignoring the cube's orientation in space, only need to turn the up (U), right (R), and front (F) faces, and don't need to turn the down (D), left (L), and back (B) faces.

A move is represented by a face, one of the letters U, R, F, followed by a direction: clockwise (empty string or space ), counterclockwise (apostrophe '), or 180 degrees (2). A cube rotation is represented as one of x (rotating the entire cube wrt R face), y (rotating the entire cube wrt U face), and z (rotating the entire cube wrt F face).

enter image description here (credit: J Perm)

enter image description here (credit: Ibero Rubik)

From the previous example, U move is equivalent to D y, meaning the result of turning the top face clockwise is indistinguishable from the result of turning the bottom face clockwise and then rotating the entire cube clockwise wrt the top face.

It is possible to rewrite algorithms with cube rotations into algorithms without cube rotations by appropriate substitution of all following face rotations. For example, y F is equivalent to R, and y U is equivalent to U.

Your task is given an input 2x2 algorithm, rewrite it using only U, R, and F moves, and without cube rotations.


I know this notation is probably confusing to people not familiar with it, so let me know how I can clarify the post.

\$\endgroup\$
0
\$\begingroup\$

The Smallest Grammar Problem


Here is a write-up for the main site.

Some changes I want to add are:

  1. You can use any language.
  2. You must formally prove the Big-O of the worst case of your algorithm in your answer.
  3. You must formally prove the correctness of your algorithm as well.

As far as running the code, that's up to the viewers of the page who wish to run the algorithm, as I can't reasonably be expected to compile code from so many different languages.

  1. Before I post to main, I will have a solution to the problem which provides correct answers and can check if an output of your algorithm is correct. It will be coded in Python 3.x. But since the question is about fastest algorithm, that shouldn't matter.

  2. Your algorithm only needs to provide one correct smallest grammar to a given input string (there are usually many), and it must be in standard form (see below).

  3. Therefore my Python 3.x code will enumerate all smallest grammars up to standard form.

  4. I will provide an example formal proof of my algorithm, both so that you can see what a formal proof entails and also so that we know that the solutions we're computing are indeed correct.

How does this all sound to you all? Where would you like to see improvements in the write-up? I am okay with rewriting the whole thing :)


The Smallest Grammar Problem (SGP), is defined as:

Given an input string s, compute a smallest CFG g such that L(g) = {s} generates the string and only the string s itself. Grammar size is defined as:

$$ |g| = \sum_{A \in \text{Vars}(g)} |g(A)| $$

Where the grammar is $$g = \{ A \to g(A), B \to g(B), C \to g(C), \dots \}, \\ \text{ and, } |g(A)|$$ simply takes the string length.

So the size of the grammar g is the sum of the lengths of all right hand sides (RHS's) of the production rules making up g.

All literature on this problem talks about approximation algorithms, and not one article demonstrates a decent exact smallest grammar algorithm. That is to say, computing the very thing the article is about in the first place. I would personally like to see what an exact SGP algorithm looks like. How optimal can we make it, and so on...

I have had many ideas on how to solve the problem. Every one of my attempts ended up with inefficient (exponential running time code). The question is can you make a speedy SGP algorithm.

The language of choice for speed of development is of course Python. Though these resulting programs should not be used in a production compressor for large data. Still, an exponential algoritm remains inefficient even if ported to C++.

So, the benchmark will be running time. You are to use standard Python 3.x, and not Cython, etc.

I have included below some relatively bug-free boilerplate utility code that you may wish to use. It handles the methods for enumerating substrings of a grammar and so on.

These are methods I will use in my own answer, which I am currently still designing. My approach will use what I call the "Groupoid of smallest grammars". Groupoids are heavily involved in combinatorial optimization problems at an advanced level, so from that heuristic they seem like the right structure to use. Another way to code this problem is translating it into a linear integer programming problem and representing substring conflicts using summation modulo 2 (or something like that). Though, linear programming problems open another can of worms since a lot of those problems also have hard running times.


To teach you about the problem, let's inspect some examples. Though we cannot prove that the examples are indeed smallest grammars - there are no theorems out there that tell whether a certain grammar is indeed minimal. A proven algorithm however, tells you whether or not your grammar is minimal. You will need to provide a proof of your algorithm in English / math text accompanied by relavent chunks of your algorithm.


Example 1. Take the string s = aaaa. Reduce it with B -> aa to get the CFG g = { A -> BB, B -> aa}$. Measure its size: |g| = 4 which is the same size as s and so therefore no compression happened.

Example 2. Take the string s = aaaaaa. Reduce using either B -> aaa, or C -> aa to get two smallest grammars:

$$ g = \{A \to BB, B \to aaa\} \\ g' = \{A \to CCC, C \to aa\} $$

Those, by experience and inspection, are precisely the full set of smallest grammars of the string of 6 $a$'s.

Example 3. Let s = abababab. Reduce using first B -> bab then C -> ab.

You get:

$$ g = \{A \to aBaB, B \to bab \}, |g| = 7 \\ g' = \{A \to CCCC, C \to ab \}, |g| = 6 \\ $$

So as you can see, a naive greedy algorithm can quite easily make wrong min / max guesses and come up with a resulting grammar that is not optimal.

Define a grammar to be reduced if no substring of length 2 or more occuring within it occurs more than once.

Reduced does not imply smallest and smallest does not imply reduced. However, every smallest grammar can be reduced, without a change to its size. Thus we will call a reduced smallest grammar the standard form of the smallest grammar.


Rules

1. Your algorithm must not only solve the SGP (which is to compute at least one smallest grammar), but it must enumerate all smallest grammars, in standard form, of a given input string.
  1. You must provide a formal proof of your algoritm in your answer. I.e. a mathematical argument that it does indeed compute the output describe in rule 1.
3. Python 3.x, no Cython or C++.

The standard form requirement reduces the total number of result smallest grammars that you must list.

Code to get you started:

# pip install bidict

from bidict import bidict
# Any involved grammar in a smallest grammar algorithm will usually have unique RHS's and unique
# variables on the left.  So it's a perfect use case for a bidirectional dictionary.  Using
# one should speed up the code greatly, otherwise we have to loop through dict values or create
# an inverse dictionary on the fly.

class Grammar:
    def __init__(self, s:str):
        """
        Start out with the trivial grammar g = {S -> s}.
        """        
        self._alphabet = set(s)
        self._previousVar = 'A'
        A = self.new_variable()
        self._start = A
        self._definition = bidict({ A : s })   # Bidict is useful, we do use the inverse lookup
        
    def grammar_size(self):
        """
        This is the standard definition of grammar size (cost) used in all literature
        with regards to the smallest grammar problem.  Minimizing this means you've found
        a smallest grammar for the given input string s.
        """
        size = 0
        for A, rhs in self._definition.items():
            size += len(rhs)
        return size
    
    def __getitem__(self, A):
        """
        Compute one iteration of expansion at a variable only.
        """
        return self._definition[A]
    
    def fully_expanded_string(self, s=None, memo=None):
        """
        Fully expand the a string passed in.  Could be a variable or a string of mixed
        variables and terminals.  Any string really.  If variables of this grammar
        occur within the string, they are fully expanded to what the grammar defines
        them to be expanded to, recursively.
        """
        if memo is None:
            memo = {}
        if s is None:
            s = self._start
        exp = ''
        for x in self._definition[s]:
            if x in self._definition:
                exp += self.fully_expanded_string(x)
            else:
                exp += x
        memo[s] = exp
        return exp        
    
    def __repr__(self):
        """
        The obvious representation for debugging / showing results.
        """
        rep = ''
        for A, rhs in self._definition.items():
            rep += A + ' ---> ' + rhs + '\n'
        rep = rep[:-1]  # remove last newline
        return rep
        
    def __str__(self):
        return repr(self)
        
    def new_variable(self):
        """
        Take the first unicode character that is not already in the grammar's alphabet.
        So it will eventually take weird-appearing characters, but who cares.  I think this
        methodology beats escape or delimit characters.  However, you're also limited to a 
        maximal alphabet size that is the Unicode character set.  That's usually just fine.
        If not, then what on Earth are you compressing ? :)
        """        
        X = self._previousVar
        while X in self._alphabet:
            X = chr(ord(X) + 1)            
        self._alphabet.add(X)
        self._previousVar = X
        return X
    
    def greedily_reduce(self):
        """
        A grammar is defined to be reduced if no substring of length >= 2 occurs twice, anywhere
        within the grammar.  There are many paths to a reduced grammar.  The smallest grammar
        problem involves taking the correct reduction path such that the resulting grammar is
        indeed minimal in size.  Greedy algorithms are known not to work in general for producing
        a smallest grammar.  However, they can easily produce a reduced grammar as you can witness.
        A smallest grammar is not necessarily reduced, though there exists a smallest grammar which
        is the reduction of that smallest grammar.  Reducing a smallest grammar would involve
        compressing all substrings of length 2 that occur exactly twice. g = {S -> abab} has the 
        same size as g' = {S -> AA, A -> ab}, namely 4.  Thus reducing a smallest grammar does not
        reduce the size (obviously), but instead puts it into a "standard form", which might be
        useful to your algorithm.
        """
        R = self.repeating_disjoint_substring_indices()                
        while len(R) > 0:
            m = self.arbitrary_greedy_max_function(R)                        
            
            if m not in self._definition.inv:
                M = self.new_variable()
            else:
                M = self._definition.inv[m]
                
            for A, indices in R[m].items():
                subtract = 0
                for i in indices:
                    rhs = self._definition[A]
                    self._definition[A] = rhs[0:i-subtract] + M + rhs[i+len(m)-subtract:] 
                    subtract += len(m) - 1                         
            self._definition[M] = m
            R = self.repeating_disjoint_substring_indices()
            
    def arbitrary_greedy_max_function(self, R:dict):
        """
        Seems like a good choice.  The total coverage of a substring if you were to compress it
        into a grammar rule.
        For example:
              If g = {A -> BaBaBaCC, B -> CCC, C -> aaa} then (3 Ba's) * |Ba| = 3 * 2 = 6 is maximal.
        """        
        total_indices = lambda rule_indices: sum(len(x) for x in rule_indices.values())
        return max(R.keys(), key=lambda x: len(x) * total_indices(R[x]))        
            
    
    def repeating_disjoint_substring_indices(self, min_len=2):
        """
        If there is overlap, this algorithm clearly does a leftmost packing.
        Same as `disjoint_substring_indices()` except we compute only the
        substrings that occur >= 2 times within the same rule or in two
        separate rules.
        
        Output form:
        {
           'substring1' : {
                 'A': [0, 3, 7],
                 'B': [1, 4, 8],
            },
           'substring2' :  ...
        }        
        where 'A' indicates the rule in which the indices occur, and the list is the list
        of indices within the rule RHS string where you'll find the substring occuring.
        The indices returned are such that the substrings occuring at those indices are mutually
        disjoint (they don't overlap).
        """        
        return self._repeatingSubstringIndices(min_len, lambda t, indices: indices)
    
    def repeating_substring_indices_all(self, min_len=2):
        """
        Return all substring indices even if there is overlaps among them.
        Output form:
        {
           'substring1' : {
                 'A': [0, 3, 7],
                 'B': [1, 4, 8],
            },
           'substring2' :  ...
        }        
        where 'A' indicates the rule in which the indices occur, and the list is the list
        of indices within the rule RHS string where you'll find the substring occuring.
        This includes all occurences even if two occurences overlap.
        """        
        return self._repeatingSubstringIndices(min_len, lambda t, indices: self.all_substring_indices(t))
    
    def _repeatingSubstringIndices(self, min_len=2, rule_indices_func=None): 
        """
        Output form:
        {
           'substring1' : {
                 'A': [0, 3, 7],
                 'B': [1, 4, 8],
            },
           'substring2' :  ...
        }        
        where 'A' indicates the rule in which the indices occur, and the list is the list
        of indices within the rule RHS string where you'll find the substring occuring.  Overlap
        or disjoint is governed by the rule_indices_func passed in.
        """
        S = {}        
        for A, rhs in self._definition.items():
            T = self.disjoint_substring_indices(rhs, min_len)
            for t, indices in T.items():                
                if t not in S:
                    S[t] = { A : indices }
                else:
                    S[t][A] = indices
        R = {}        
        for t, rule_indices in S.items():
            if len(rule_indices) >= 2:
                R[t] = rule_indices_func(t, rule_indices)
            else:
                for var, indices in rule_indices.items():
                    if len(indices) >= 2:
                        R[t] = rule_indices_func(t, rule_indices)
                        break
        return R
    
    @staticmethod
    def disjoint_substring_indices(s:str, min_len=2, max_len=None):
        """
        Leftmost-first packed indices of all substrings of the string s.  The substring
        occurences (indexes) are guaranteed to be of disjointly occuring substrings.
        If two occurences overlap, by for-loop logic we're taking the leftmost.  Hence
        "leftmost-first packed".
        Output form:
        {
           'substring1' : {
                 'A': [0, 3, 7],
                 'B': [1, 4, 8],
            },
           'substring2' :  ...
        }        
        where 'A' indicates the rule in which the indices occur, and the list is the list
        of indices within the rule RHS string where you'll find the substring occuring.
        The indices are such that the substrings occuring at those indices are disjoint 
        (they don't overlap).
        """
        if max_len is None:
            max_len = int(len(s)/2)   # Maximum length of a repeated substring
        S = {}
        for i in range(0, len(s)-min_len+1):
            for j in range(i+min_len, i+min(max_len, len(s))+1):
                t = s[i:j]
                if t in S:
                    if i >= max(S[t]) + len(t):
                        S[t].append(i)
                else:
                    S[t] = [i]
        return S
                
    def all_substring_indices(self, t:str):
        """
        The indices of all occurences of the given substring.  Output form:
        {
           'A' : [0, 3, 7],
           'B' : [1, 4, 8],
           ...
        }
        where 'A' indicates the rule in which the indices occur, and the list is the list
        of indices within the rule RHS string where you'll find the substring occuring.
        This includes all occurences even if two occurences overlap.
        """
        R = {}        
        for A, rhs in self._definition.items():
            for i in range(0, len(rhs)-len(t)):
                if rhs[i:].startswith(t):
                    if A not in R:
                        R[A] = [i]
                    else:
                        R[A].append(i)
        return R
    
    def include_all_possible_rules(self):
        """
        A possible rule is one such that the length of its RHS is >= 2 and fully
        expanded it occurs at least twice in the input string s.  Including all possible
        rules does not change the fact that the grammar expands to s for some starting
        variable.  In other words we still have a grammar for s, by definition, though
        some of its rules may be unused.
        """
        # So first get all disjointly repeating substrings:
        R = self.repeating_disjoint_substring_indices()
        # To "include all rules" we form a rule for each repeating substring:
        
        for r in R:
            A = self.new_variable()
            if r not in self._definition.inv:
                self._definition[A] = r
                
    
if __name__ == '__main__':
    s = 'aaaaaa'
    g = Grammar(s)
    g.greedily_reduce()
    print(g)
    print('The canonical example on a singleton alphabet.  The smallest example such that the smallest '
          f'grammar is indeed smaller than the input {s}')
    print('-----------')
    s = 'ababab'
    g = Grammar(s)
    g.greedily_reduce()
    print(g)
    print(f"This is known to indeed be a smallest grammar of {s}, by inspection.")    
    print('-----------')
    s = 'abcabcabababc'
    g = Grammar(s)
    g.greedily_reduce()
    print(g)
    print(f"Similarly, this too also is probably a smallest grammar for {s}")
    print('-----------')
    s = 'ababababbaaaaaaaabbbbaa'
    print(s)
    g = Grammar(s)
    g.include_all_possible_rules()
    g.greedily_reduce()
    s1 = g.fully_expanded_string()
    print(g)
    assert (s1 == s)
    print('A more complicated example demonstrating "including all possible rules" and then greedily reducing '
          'everything.')
    print('-----------')

Which prints:

A ---> BBB
B ---> aa
The canonical example on a singleton alphabet.  The smallest example such that the smallest grammar is indeed smaller than the input aaaaaa
-----------
A ---> BBB
B ---> ab
This is known to indeed be a smallest grammar of ababab, by inspection.
-----------
A ---> CCBBC
B ---> ab
C ---> Bc
Similarly, this too also is probably a smallest grammar for abcabcabababc
-----------
ababababbaaaaaaaabbbbaa
A ---> DDOLLLbbbO
B ---> ab
C ---> aba
D ---> BB
E ---> ba
F ---> bab
G ---> abb
H ---> bb
I ---> bba
J ---> bbL
K ---> baa
L ---> aa
M ---> aaa
N ---> LL
O ---> bL
A more complicated example demonstrating "including all possible rules" and then greedily reducing everything.
-----------
\$\endgroup\$
1
  • 2
    \$\begingroup\$ The explanation is kind of long, and I would suggest separating a section that clarifies the task and input-output format. \$\endgroup\$
    – okie
    Apr 30 at 7:45
0
\$\begingroup\$

Cleaning KoTH

Clean up a 50x75 room with a JSbot before there is too much junk!

The Challenge

A 50x75 room is cluttered 375 items, each taking up 1 cell of space. Create a JSbot that takes an array as an input to clean up the room. If the bot is on a cell with junk in it, the junk is automatically removed.

Each bot will be paired against another bot. One bot will be the "cleaner," the other will be a "disorganizer." The cleaner is exactly what it is. The disorganizer, every turn, has a 10% chance of being able to place a junk where it is.

The disorganizer wins if the amount of junk reaches 400 or more, while the cleaner wins if the amount of junk reaches 0.

Rules

  • Preset commands you may use are:

    • left(bot_name) Moves left 1 cell (x-1)
    • right(bot_name) Moves right 1 cell (x+1)
    • up(bot_name) Moves up 1 cell (y+1)
    • down(bot_name) Moves down 1 cell (y-1)
  • Storing data in your bot is allowed!

Example

Here is an example of a bot, and how to format it.

bots.ConfusedBot = { // bots.Foo where Foo is the name of your bot
    x: 0 // 0 is the center
    y: 0 // 0 is the center
    clean: function (array) { // cleaning function
        left("ConfusedBot");
        right("ConfusedBot");
        up("ConfusedBot");
        down("ConfusedBot");
    }
    sabotage: function (array) { // disorganizing funcction
        up("ConfusedBot");
        down("ConfusedBot");
        left("ConfusedBot");
        right("ConfusedBot");
    }
}

Comments and/or concerns? Comment down below to notify me.

\$\endgroup\$
2
  • \$\begingroup\$ I'd recommend giving this a read. KotHs are one of the hardest types of challenges to get right (if not the hardest). Currently it doesn't look like there's much strategy at all here. \$\endgroup\$ May 3 at 14:34
  • \$\begingroup\$ @RedwolfPrograms Yep, that's been a problem for all of these. I will edit it to make it more strategic. \$\endgroup\$ May 3 at 14:41
0
\$\begingroup\$

Base Guard (Rewritten)

Base: part 1

This is part 2, Strongly suggest you go try out the first one if you haven't tried it.

Story

As one of the solvers, You've managed to get to the door of the base heaven. In front of the door stands the base guard @Lyxal, he was angry that you all just left the encoded text on the ground, he deems you to clean(decode) the ground before joining the party, those who are irresponsible gets no ticket!

Task

You will get 2 inputs

  • First being X which is a non-negative integer in base of base list.
  • Second being base which is a list of bases.
  • bases range from 1 ~ 10
  • The base will contain at least one not 1 base
  • answer should be in the base 10

Example:

X, [bases] -> answer
110 ,[2] -> 6
30 ,[2,4] -> 6
2100 ,[2,3] -> 30

You may want to look at part 1 for more detail

Rule

Basic Rules

Satisfy Lyxal with the shortest code, because a long code indicates that you are lazy and not doing your best!

Sandbox

  • Is this count as a dup of part 1?
  • Any extra suggestions?
  • Lyxal are you willing to become the guard? Or anyone else would like to be the guard?
\$\endgroup\$
5
  • \$\begingroup\$ You say lowercase alphabet, but your example uses capital F. Also, this would be a duplicate of the first part because handling higher numbers shouldn't require much modification from part 1, and indexing into the base digits is a pretty trivial extra step that doesn't add anything to the challenge anyway. \$\endgroup\$
    – hyper-neutrino Mod
    May 4 at 5:23
  • \$\begingroup\$ No tickets for anyone unless they impress me. \$\endgroup\$
    – lyxal
    May 4 at 5:25
  • \$\begingroup\$ @hyper-neutrino Then I will rewrite this challange to somethin more creative. \$\endgroup\$
    – okie
    May 4 at 6:04
  • \$\begingroup\$ I'm good with guarding \$\endgroup\$
    – lyxal
    May 4 at 6:46
  • \$\begingroup\$ @Lyxal Excellent \$\endgroup\$
    – okie
    May 4 at 6:48
0
\$\begingroup\$

Given a subset of {+,*,<,=,E,A,(constant),(variable)}. For most of the subsets, use the symbols to express Riemann hypothesis.

Output format flexible. Most subset, and on tie, smallest (code length+sum symbols used) in each language wins. (So there'll also be a winner in Text)

You can also choose to focus on sum symbols used, and claim that you answered in Custom, counting like a 0-byte solution.

\$\endgroup\$
0
\$\begingroup\$

Regex, ASCII-literal

Objective

Execute the given regex for the given text. The regex is in a special scheme I made.

Motivation

For most regexes the usual languages support, they assign some printable ASCII characters for special instructions. For POSIX as an example, * is the Kleene star, . matches an arbitrary character, and ( and ) groups a subexpression. Because of this, If such characters themselves were to be matched, I must escape them by a backslash \. This may cause the regex seem obfuscated. Not to mention that in most languages, backslashes must be escaped themselves like \\.

So instead of printable ASCII characters, I chose ASCII control characters to assign some special instructions.

Inputs

Two strings indicating the regex and the text. They are assumed to consist of ASCII characters. Otherwise, the entire challenge falls in don't care situation.

Output

A list of pairs of integers. Each pair indicates the starting position and the ending position of each strings matched.

Indexing is implementation-defined, but preferred to be zero-indexed.

Each pair shall be left-inclusive of its indicated string. The right, however, is implementation-defined whether inclusive or exclusive. (Exclusive is preferred)

Regex

Here, I shall call a unit of regex a packet.

For all characters within \x20\x7E, it is a minimal packet that matches itself.

For control characters (with some exceptions), however, it has a special functionality. It classifies to one of:

  • A minimal packet.

  • A parenthesis. A pair of parentheses group packets into one packet.

  • A unary operator. They accept one packet, and they all are suffixes. They have higher precedence to all binary operators.

  • A binary operator. They accept two packets, they all are infixes, and they all associate to right.

The regex munches each strings matched. In other words, the matched strings cannot overlap.

If an empty string is matched, it shall be ignored. In other words, all matched strings shall be nonempty.

The regex is case-sensitive by default.

Text

The lines of the text are delimited by \n, \f, \r, and \v.

The words of the text are separated by ASCII whitespaces ( and \t, in addition to the above).

Control characters

  • \x00 (NUL; Null) has an implementation-defined functionality. It's because in some languages, strings are null-terminated.

  • \x01 (SOH; Start of Header): Minimal packet. It matches the start of a line.

  • \x02 (STX; Start of Text): Left parenthesis corresponding to ETX.

  • \x03 (ETX; End of Text): Right parenthesis corresponding to STX. Concatenates the packets inside.

  • \x04 (EOT; End of Transmission): Minimal packet. It matches the end of a line.

  • \x05 (ENQ; Enquiry): Left parenthesis corresponding to ACK or NAK.

  • \x06 (ACK; Acknowledgement): Right parenthesis corresponding to ENQ. It serves as an arbitrary-input OR gate. The first alternative that matches shall be matched.

  • \x07 (BEL; Bell): Unary operator. It "inverts" its operand, like this:

    • If its operand is a minimal packet that matches a single character, it matches a character the packet doesn't match.

    • It commutes with a unary operator.

    • It distributes to a binary operator.

    • It distributes to packets within parentheses.

    • Otherwise, it has no effect.

  • \x08 (BS; Backspace): Minimal packet. It matches an arbitrary ASCII whitespace.

  • \x09 (HT; Horizontal Tab): Minimal packet. It matches \t.

  • \x0A (LF; Line Feed): Minimal packet. It matches \n.

  • \x0B (VT; Vertical Tab): Minimal packet. It matches \v.

  • \x0C (FF; Form Feed): Minimal packet. It matches \f.

  • \x0D (CR; Carriage Return): Minimal packet. It matches \r.

  • \x0E (SO; Shift Out): Minimal packet. It matches an arbitrary lowercase Latin letter.

  • \x0F (SI; Shift In): Minimal packet. It matches an arbitrary uppercase Latin letter.

  • \x10 (DLE; Data Link Escape): Unary operator. Its operand shall be matched case-insensitive.

  • \x11 (DC1; Device Control One): Unary operator. Its operand shall be matched zero or more times. It is greedy.

  • \x12 (DC2; Device Control Two): Unary operator. Its operand shall be matched one or more times. It is greedy.

  • \x13 (DC3; Device Control Three): Unary operator. Its operand shall be matched two or more times. It is greedy.

  • \x14 (DC4; Device Control Four): Unary operator. Its operand shall be matched zero or one time. It is greedy.

  • \x15 (NAK; Negative Acknowledgement): Right parenthesis corresponding to ENQ. It is equivalent to ACK BEL.

  • \x16 (SYN; Synchronous Idle): Binary operator. If and only if the operands match the same string, it shall match the string. Has higher precedence to CAN, and has lower precedence to EM.

  • \x17 (ETB; End of Transmission Block): Minimal packet. Matches either the start of a word or the end of a word.

  • \x18 (CAN; Cancel): Binary operator. Two-packets version of ENQ-ACK. Has the lowest precedence.

  • \x19 (EM; End of Medium): Binary operator. Treats surrounding characters as escaped, and matches a character within the range they indicate, both inclusive. If the left operand has higher ASCII code point than the right operand, the range wraps around the ASCII codepage.

  • \x1A (SUB; Substitute): Minimal packet. Matches an arbitrary character.

  • \x1B (ESC; Escape): As a prefix, this character is used to escape a control character. An escaped ASCII character, including DEL (but not necessarily including NUL), shall match itself.

  • \x1C (FS; File Separator): Minimal packet. Matches a hexadecimal digit, case-insensitive.

  • \x1D (GS; Group Separator): Minimal packet. Matches a decimal digit.

  • \x1E (RS; Record Separator): Minimal packet. Matches an octal digit.

  • \x1F (US; Unit Separator): Minimal packet. Matches a binary digit.

  • \x7F (DEL; Delete): Unless escaped by ESC, this character shall be skipped. It doesn't even count as a packet.

Errors

Upon the following conditions, it shall fall in an implementation-defined behavior to indicate an error:

  • Unpaired parenthesis

  • Unary/Binary operator without an operand

Examples

(WIP)

Ungolfed solution

Haskell

(WIP)

Sandbox questions

  • Is this challenge too hard or cumbersome?

  • Do you have better ideas for the functionalities of control characters?

\$\endgroup\$
1
  • \$\begingroup\$ Suggest map to usual RegEx, and explanation for those whthout direct map \$\endgroup\$
    – l4m2
    May 4 at 11:13
0
\$\begingroup\$

Radio station hopping

You are listening to a car radio. You are pressing seek up/down, moving you to the next frequency some radio station broadcasts on, to avoid all this pointless music and listen to all the ads, or vice versa. But there is a tendency of these broadcasts to have your radio jump to another frequency, where signal of that radio station is stronger. So, suppose this radio station A broadcasts at 99, 100 and 101 MHz with 100 MHz having the strongest signal at your place. The moment you reach 101 MHz, radio will jump to 100 MHz.

Because of that, you can get trapped. Suppose there is one extra radio station B, broadcasting only at 102 MHz. The moment you are stuck at the station A, you can never listen to station B again - if you try going with frequency down, you will hit 99 and jump to 100, if you go up you reach 101 and jump to 100 again... never escaping that trap.

But if there is yet another station C at 99.5 and 98.5 MHz with latter being the strongest, you can listen to all 3 radios again - starting from B you get down to A, then down to C, then pressing down loops you back again to the highest frequency.

So, you start wondering - can I listen to all radio stations at least once if I start at any frequency? And will I be able to endlessly cycle through all of them, or listen to all just once before getting cut off some stations?

Your task:

Get a list of radio stations, along with a designation of which has the strongest signal, in any reasonable format (1). Return one of three values to distinguish whether you can cycle through all stations indefinitely, you can cycle through all stations once or you cannot reach all stations from any starting point. Again in any reasonable format (2).

(1) Test cases have inputs as radio stations separated by semicolon, for each radio station, the strongest broadcast for the station is first, entries separated by comma. You can pick anything else as your input format, along with any reasonable extra information you would like - for example number of radio stations, number of channels each station broadcasts at etc. You can use integers (eg just multiply everything in example by 10).

(2) Test cases have output as 1 - cycle all, 2 - cycle once, 3 - cannot reach all stations. You can return anything reasonable to distinguish these three options, as long as you return/print the value. You must return, eg "you can cycle all" crashing or never stopping is NOT allowed.

Test cases:

input: 102; 100, 99, 101 output: 2

input: 102; 100, 99, 101; 98.5, 99.5 output: 1

input: 100, 99, 101; 103, 102, 104 output: 3

input: 100, 99, 101; 103, 102, 104; 101.5, 99.5, 103.5 output: 1

input: 100, 99; 99.5, 100.5; 102, 103; 102.5, 101.5 output: 3

May the shortest code win.

Tags: code-golf
Any suggestions? (and is this a duplicate maybe, I haven't found it but I don't know what exactly to search for here)

\$\endgroup\$
0
\$\begingroup\$

Solve any NPC problem. Shortest code win.

Sandbox Notes

  • Will every submission tend to single NPC problem?
  • How many builtins are known to solve this in Mathematica?
  • Do 0-byte solution exist?
\$\endgroup\$
3
  • \$\begingroup\$ I think this is too broad to be a good challenge \$\endgroup\$
    – pxeger
    May 4 at 12:44
  • \$\begingroup\$ Dyalog Extended can solve it in two bytes: ⌂X (Knuth's X algorithm which solves the Exact Cover problem). \$\endgroup\$
    – Bubbler
    May 6 at 8:59
  • \$\begingroup\$ @Bubbler Lots of language will have builtin for this question I guess \$\endgroup\$
    – l4m2
    May 6 at 17:45
0
\$\begingroup\$

Determine tournament winners

Given a table of names and per round scores, arrange the names in descending order of their Neustadtl Sonneborn–Berger score.

Challenge

A player's Sonneborn-Berger score(which we will from now on refer to as "tiebreak score"), is the sum of the points they received in each round (\$x_{i}\$), multiplied by the points that each their round opponent achieved totally via standard scoring(\$p_{i}\$), given round count \$n\$.

Effectively, each player's score is: $$ \sum_{i=1}^n p_ix_i. $$

Your challenge is to calculate this score for each player and arrange them in increasing order of ordinary score, and then use the tiebreak score to resolve any ties in points.

From Wikipedia:

here is the crosstable of the 1975–80 World Correspondence Chess Championship Final (here cs indicates conventional score, ns Neustadtl score):

                  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  cs   ns
1.  Sloth         X ½ ½ 1 ½ ½ 1 1 ½  1  ½  1  1  1  1  11   69.5
2.  Zagorovsky    ½ X 0 ½ 1 ½ 1 1 1  ½  1  1  1  1  1  11   66.75
3.  Kosenkov      ½ 1 X ½ ½ ½ ½ ½ 1  1  ½  1  1  1  1  10½  67.5
4.  Khasin        0 ½ ½ X ½ 1 ½ 0 1  1  ½  1  ½  1  ½  8½   54.75
5.  Kletsel       ½ 0 ½ ½ X ½ ½ ½ ½  0  1  1  ½  1  1  8    47.75
6.  De Carbonnel  ½ ½ ½ 0 ½ X ½ ½ 0  1  ½  ½  0  1  1  7    45.25
7.  Arnlind       0 0 ½ ½ ½ ½ X ½ 1  0  ½  ½  1  1  ½  7    42.5
8.  Dunhaupt      0 0 ½ 1 ½ ½ ½ X 0  ½  1  0  1  ½  1  7    41.5
9.  Maedler       ½ 0 0 0 ½ 1 0 1 X  1  ½  ½  ½  ½  1  7    41.5
10. Estrin        0 ½ 0 0 1 0 1 ½ 0  X  1  1  1  0  1  7    40.5
11. Walther       ½ 0 ½ ½ 0 ½ ½ 0 ½  0  X  0  1  ½  1  5½   33.25
12. Boey          0 0 0 0 0 ½ ½ 1 ½  0  1  X  ½  ½  1  5½   28.5
13. Abramov       0 0 0 ½ ½ 1 0 0 ½  0  0  ½  X  ½  1  4½   24.75
14. Siklos        0 0 0 0 0 0 0 ½ ½  1  ½  ½  ½  X  1  4½   22.75
15. Nun           0 0 0 ½ 0 0 ½ 0 0  0  0  0  0  0  X  1    7.75

As an example, Sloth's score is calculated as: 0.5*11 + 0.5*10.5 + 1.0*8.5 + 0.5*8.0 + 0.5*7.0 + 1.0*7.0 + 1.0*7.0 + 0.5*7.0 + 1.0*7.0 + 0.5*5.5 + 1.0*5.5 + 1.0*4.5 + 1.0*4.5 + 1.0*1.0 = 69.5

\$\endgroup\$
0
\$\begingroup\$

Surprisingly, I don't think there has been a question about Whyte notation before. I suspect the ASCII challenge is a bit too easy, but not sure how many people are interested in a graphical challenge. Thoughts? Comments?

Whyte notation

Write a program which turns a string containing a valid (subset of) Whyte notation into an ASCII/graphical representation.

Whyte notation is a system for succinctly describing the arrangement of wheels on a steam locomotive. For the purpose of this challenge, a valid input consists of:

  • one or more wheelsets, joined by a + symbol
  • where each wheelset is of the form l-d1[-d2...]-t, where:
    • l is an integer specifying the number of leading wheels (small wheels at the front of the wheelset that aren't powered, but help keep it on the tracks)
    • d1 (and d2 etc) is the number of driving wheels (large wheels powered by a steam engine) coupled together. If there is more than one number, it means multiple coupled sets of driving wheels. (All the sets are powered by the same engine, but using different sets of cylinders - divided drive)

(Multiple wheelsets means an articulated locomotive, that is, two engines powered by the same boiler, but able to rotate independently, which is good for getting powerful locomotives around tight bends).

For instance:

  • 2-4-0 means a locomotive with 2 leading wheels (1 axle), 4 driving wheels (2 axles), and no trailing wheels. We can represent it like this: o-O=O
  • 4-8-8-2 means a locomotive with 4 leading wheels, two coupled sets of 8 driving wheels, and 2 trailing wheels. We can represent it like this: o-o-O=O=O=O-O=O=O=O-o
  • 2-4-2+2-4-2 means an articulated locomotive with two wheelsets. Each one consists of 2 leading wheels, 4 driving wheels and 2 trailing wheels. We can represent it like this: o-O=O-o:o-O=O-o

A Baldwin 2-4-0 locomotive: 2 leading wheels, 4 driving wheels, no trailing wheels

Image: A Baldwin 2-4-0 locomotive: 2 leading wheels, 4 driving wheels, no trailing wheels.

Input

Input is a string (or equivalent) that is valid in this subset of Whyte notation. You may assume:

  • Leading and trailing wheel counts are even integers in the range 0-6 inclusive.
  • Driving wheel counts are even integers in the range 2-14 inclusive.
  • There are 1-4 coupled sets of driving wheels per wheelset.
  • There are 1-2 wheelsets.

Output (ASCII)

The rules for output are thus:

  • the train is always facing left, so the leading wheels are at the start of the input and output strings.
  • leading and trailing wheels are represented as one o per 2 wheels, joined by -
  • each set of driving wheels are represented as one O per 2 wheels, joined by =.
  • sets of driving wheels are joined by -
  • wheelsets are joined by :

Output (graphical)

Alternatively, you may output a graphical representation of a similar type: a series of circles from left to right. At a minimum:

  • all wheel circles must have a dark stroke and light fill, with the stroke no more than 10% the width of the circle
  • the lowest point of all wheel circles must be equal (they all touch the same imaginary track)
  • all wheel circles of a given type must be the same size
  • leading/trailing wheels must have a diameter in the range 20-50% of the diameter of driving wheels
  • coupled sets of driving wheels must be indicated by a horizontal line connecting their centres*.
    • * you may offset this line up to 40% of a driving wheel diameter in any direction to maintain artistic integrity
  • non-coupled wheels must not be connected, and have a space in the range 25-50% of the diameter of a driving wheel between them.
  • for an articulated locomotive, the two wheelsets must be separated by a space of between 100% and 150% of a driving wheel diameter.

Scoring

This is code golf, shortest program in bytes wins. Standard rules/loopholes apply. There are two categories: ASCII output and graphical output.

\$\endgroup\$
1
  • \$\begingroup\$ Make it one or the other, otherwise it's too confusing. \$\endgroup\$
    – emanresu A
    May 10 at 9:41
1
100 101
102
103 104
117

You must log in to answer this question.

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