515
\$\begingroup\$

What is the Sandbox?

This "Sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on 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.

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

\$\endgroup\$
0

3273 Answers 3273

1
97 98
99
100 101
110
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\$

Determine if a dot(comma) program halts

Posted to main

\$\endgroup\$
1
  • \$\begingroup\$ this could be an interpreter challenge, it's interpreting dotcomma without queue, I/O, or loops, then returning whether there would be a loop. That's more complicated then some interpreter challenges. \$\endgroup\$ – Wezl Feb 10 at 16:47
0
\$\begingroup\$

The Printer Booklet Sequence

You may know of a "booklet" setting often present on printers, where the pages are printed in a way that they can be simply folded down the middle so that the pages are in the right place to form a booklet, as demonstrated in this diagram:

Diagram of booklet printing

The logic to construct the booklet for \$ p \$ pages is:

  • Allocate \$ \lceil \frac p 4 \rceil \$ sheets of paper
  • Fill the sheets from first to last, printing on the outside right, then inside left of each page
  • Fill the sheets from last to first, printing on the inside right, then outside left of each page

Or, more abstractly:

  • Allocate \$ p \$ blank slots, rounded up to the nearest multiple of 4
  • Fill the 2nd and 3rd elements of each group of 4 pages with the next page until all the groups of 4 have been filled
  • Then, in reverse, fill the 4th then 1st elements of each group with the next page

Now consider how we might represent these. If we number the pages \$ 1 \text{ to } p \$, and use \$ 0 \$ to represent blank (unprinted) pages, then this is how the page arrangements for booklets of length \$ p = 1 \$ to \$ 16 \$ would look:

0 1 0 0
0 1 2 0
0 1 2 3
4 1 2 3
0 1 2 0 0 3 4 5
0 1 2 0 6 3 4 5
0 1 2 7 6 3 4 5
8 1 2 7 6 3 4 5
0 1 2 0 0 3 4 9 8 5 6 7
0 1 2 0 10 3 4 9 8 5 6 7
0 1 2 11 10 3 4 9 8 5 6 7
12 1 2 11 10 3 4 9 8 5 6 7
0 1 2 0 0 3 4 13 12 5 6 11 10 7 8 9
0 1 2 0 14 3 4 13 12 5 6 11 10 7 8 9
0 1 2 15 14 3 4 13 12 5 6 11 10 7 8 9
16 1 2 15 14 3 4 13 12 5 6 11 10 7 8 9

Your task is to compute all of these layouts concatenated together as one sequence, which starts:

0 1 0 0 0 1 2 0 0 1 2 3 4 1 2 3 0 1 2 0 0 3 4 5 0 1 2 0 6 3 4 5 0 1 2 7 6 3 4 5 8 1 2 7 6 3 4 5 0 1 2 0 0 3 4 9 8 5 6 7 0 1 2 0 10 3 4 9 8 5 6 7 0 1 2 11 10 3 4 9 8 5 6 7 12 1 2 11 10 3 4 9 8 5 6 7 0 1 2 0 0 3 4 13 12 5 6 11 10 7 8 9 0 1 2 0 14 3 4 13 12 5 6 11 10 7 8 9 0 1 2 15 14 3 4 13 12 5 6 11 10 7 8 9 16 1 2 15 14 3 4 13 12 5 6 11 10 7 8 9

You can find the first million terms of the sequence here. I can't find it on the OEIS, but plan to submit it.

As usual for challenges, your code should either:

  • Take no input, and output the terms infinitely,
  • Take \$ n \$ as input, and output the \$ n \$th term (0- or 1-indexed), or
  • Take \$ n \$ as input, and output the first \$ n \$ terms

Here is an un-golfed reference implementation.

Rules


Meta

  • Is this a duplicate? It's definitely not directly, but there may be another challenge that gives a similar sequence, just framed differently?
  • Is this clear enough?
  • What other tags should I add?
  • Any other feedback?
\$\endgroup\$
1
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\$ – caird coinheringaahing 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\$ – caird coinheringaahing Apr 25 at 17:28
0
\$\begingroup\$

Ambigious Chemical Formula

Losing capital of a chemical formula, it may become ambigious: co can be both CO or Co.

Given an input consisting of a-z0-9, where 0 can only stand behind 1-9. Check whether it's ambigious, unambigious, or impossible. Return 3 different values for them. Shortest code win.

Examples:

co     - ambigious
2h83o6 - unambigious
li     - unambigious
l      - impossible
cli    - ambigious
c10h7o - unambigious

One-sentence meaning: Is there zero, one or multiple ways to split input into concation of the following strings:

0,1,2,3,4,5,6,7,8,9,H,He,Li,Be,B,C,N,O,F,Ne,Na,Mg,Al,Si,P,S,Cl,Ar,K,Ca,Sc,Ti,V,Cr,Mn,Fe,Co,Ni,Cu,Zn,Ga,Ge,As,Se,Br,Kr,Rb,Sr,Y,Zr,Nb,Mo,Tc,Ru,Rh,Pd,Ag,Cd,In,Sn,Sb,Te,I,Xe,Cs,Ba,La,Ce,Pr,Nd,Pm,Sm,Eu,Gd,Tb,Dy,Ho,Er,Tm,Yb,Lu,Hf,Ta,W,Re,Os,Ir,Pt,Au,Hg,Tl,Pb,Bi,Po,At,Rn,Fr,Ra,Ac,Th,Pa,U,Np,Pu,Am,Cm,Bk,Cf,Es,Fm,Md,No,Lr,Rf,Db,Sg,Bh,Hs,Mt,Ds,Rg,Cn,Nh,Fl,Mc,Lv,Ts,Og
\$\endgroup\$
3
  • 2
    \$\begingroup\$ This looks like an interesting challenge, but in its current form needs a lot more details (as do most of your sandbox posts - I'd recommend using a question template to make sure you've always included everything). For people who don't know chemistry, it's lacking crucial information: what is the exact syntax of a chemical formula, and how does one know it's ambiguous? \$\endgroup\$ – pxeger Apr 22 at 16:28
  • 1
    \$\begingroup\$ I also think it would be more interesting if the element list were provided as input. Otherwise most of the actual golfing part of the challenge boils down to compressing the list (or finding a short built-in to output them) \$\endgroup\$ – pxeger Apr 22 at 16:29
  • \$\begingroup\$ @pxeger Quite unrelated to chemical though, ClI and CLi both don't fell good \$\endgroup\$ – l4m2 Apr 22 at 18:23
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\$ – caird coinheringaahing 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\$ – Redwolf Programs 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\$ – Redwolf Programs 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\$ – Redwolf Programs 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\$

Random Move 2x2 Scrambling

A simple way to scramble a 2x2x2 Rubik's cube is to make a sequence random moves. This is not how official scrambles are done, but can get pretty close to a uniform distribution of scramble states. Due to the way a 2x2 only has two layers, doing one turn on one face is equivalent (without considering the puzzle's orientation in space) to doing the same direction turn on the opposite face. For example, turning the top face clockwise moves all the pieces in relation to each other the same way turning the bottom face clockwise does. So scrambles only need to turn the top (U), right (R), and front (F) faces.

For this challenge, your program must generate a sequence of 16 moves. 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). The turn and direction should be chosen uniformly at random, however two consecutive moves cannot have the same starting letter, for example a scramble cannot contain R' R2. Moves are separated by a space.

Input

None.

Output

A random move scramble. Example scramble:

U  F' R2 F' R' F  R  F2 U' F  R2 F  U2 F' U2 F2 

This doesn't affect the challenge, but 16 is the number I read on a very old speedsolving forums post, but idk if it is actually accurate.

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

Given a black-box function f(x) which take a value x and output true for \$p(x)\$, an unknown continious monotone function(not knowing even whether it's increasing), probable; and false otherwise. Output an infinite sequence \$a_n\$ such that \$\lim_{n\rightarrow \infty}p(a_n)=0.5\$. You can assume that the result exists.

Reasonable I/O allowed. Shortest code win.

A possible solution:

for i=1..infty
    S = [i/2] * i*i*2
    for j=0..i*i*2-1
        for k=1..i
            if f(j/i-i)
                S[j]--
    print minPos([t*t for t in S])/i-i

\$\endgroup\$
7
  • \$\begingroup\$ So we are given two functions f and p and need to define an infinite sequence? \$\endgroup\$ – Quelklef Mar 26 at 1:55
  • \$\begingroup\$ You're not given p, and you're to find a such that p(a)=0.5 \$\endgroup\$ – l4m2 Mar 26 at 5:58
  • \$\begingroup\$ If we are not given p, how are we supposed to find a? Do you want us to generate an a that works for every p? \$\endgroup\$ – Quelklef Mar 26 at 6:51
  • \$\begingroup\$ @Quelklef Try some a and adjust till probable is 0.5 \$\endgroup\$ – l4m2 Mar 26 at 7:19
  • 1
    \$\begingroup\$ I completely do not understand. Is it possible you could provide an example solution in your problem? That may help others confused like me. \$\endgroup\$ – Quelklef Mar 26 at 15:13
  • \$\begingroup\$ Say, \$ p\left(x\right) = \frac{4\pi + 2\arctan\left(x\right)}{5\pi} \$. How can you find out such a sequence \$ a_n \$ let \$ \lim_{n\to\infty}p(a_n)=0.5 \$ \$\endgroup\$ – tsh Mar 29 at 8:44
  • \$\begingroup\$ Even if we can safely assume that there is a value \$x\$ that \$p\left(x\right)=0.5\$, I don't think anyone can provide sequence would even convergent with a non-zero probable. \$\endgroup\$ – tsh Mar 29 at 8:51
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\$ – Redwolf Programs 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\$ – fasterthanlight May 3 at 14:41
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)

New contributor
Zizy Archer is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
0
\$\begingroup\$

CGCC sings a song together

This is a challenge, where the answers will aim to, together, output the lyrics to this beloved 80s song.

This is the full lyrics of the song, line by line. The first answer will contain a program that will output the first line of the song (We're no strangers to love). The second will do the same, but for the second line (You know the rules and so do I) and so on. Some answers (the 7th, 14th, 22nd, 29th, 36th, 45th, 51st, 54th, 61st and 68th) will output a blank line.

Each answers' program, however, must be irreducible, meaning that it must not output the correct line if any characters are removed.

  • print('We're no strangers to love') is an irreducible Answer 1 in Python 3
  • if 1: print('We're no strangers to love') is not, as we can remove if 1: and it'll still output the first line

Let \$\bar x_i\$ be the arithmetic mean of the lengths of the first \$i\$ lines, to 1 decimal place. This sequence begins \$26, 28, 32, 34, 34.6, 33\$ and converges to \$\bar x_{74} = 24.3\$ by the end of the song. Each answer has a score, which will eventually determine the overall winner. The score for the \$i\$th answer is defined as:

If the \$i\$th answer is \$n\$ bytes long, its score is \$|n - \bar x_i|\$

So, if the first answer is 10 bytes long, its score is \$16\$, and if the 72nd answer is 2 bytes long, its score is \$|2 - 24.2| = 22.2\$. A user's overall score is the arithmetic mean of the scores of all their answers. The user with the lowest overall score wins.

The full sequence of \$\bar x_i\$; the left column is \$i\$, the right is \$\bar x_i\$. Collapse the "Arguments" element for easier viewing.


Rules

  • You may either:

    • Output the line to STDIN, or your language's closest alternative; or,
    • Return the line from a function
  • You should take no input, aside from an optionally empty input

  • Languages may only be used once. This includes different versions of a language, such as Python 2 and Python 3. Generally, if two languages are considered versions of each other, such as Seriously and Actually, then only one is allowed to be used.

  • You may not post 2 answers in a row

  • You must wait 1 hour between answers

  • The challenge will end when the 74th answer is posted, at which point I will accept an answer of the winner's choice


Meta

  • Is this clear enough?
  • Is there a better text to use?
    • I chose the rickroll because it's well known, it's long enough to have a decent sized chain without being so long as to become boring
    • However, it is fairly repetitive at times, which I fear could lead to some boring answers
  • Is this an challenge? The answers don't actually depend on the previous answer, but taken in isolation, each answer doesn't have the same "meaning" as the answers all together
  • Tags are , and . Any others?
  • Any further feedback?
\$\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 yesterday
  • \$\begingroup\$ @Bubbler Lots of language will have builtin for this question I guess \$\endgroup\$ – l4m2 yesterday
0
\$\begingroup\$

Square chunk my matrix (Title suggestions welcome)

I have no context for this.

Your challenge is to write a function/program that takes a matrix m and a number n as input and:

Splits the matrix into nxn chunks

Replaces each chunk with the most common value in that chunk (In case of a tie, any of the tied values is fine).

Outputs the resulting matrix.

Example:

0 1 0 1
0 0 1 1
0 0 0 0
0 0 1 1, 
2

Divide into chunks:

0 1|0 1
0 0|1 1
---+---
0 0|0 0
0 0|1 1

Take the most common value in each sub-matrix

0|1
-+-
0|0

So

0 1
0 0

is the result!

Note: You can assume that m's size will always be divisible by n.

Testcases

0 1 2 1 2 1
2 2 1 0 2 2
2 1 2 0 1 0
0 0 1 0 3 2
3 0 2 0 3 1
1 0 3 2 0 1, 
3 =>
2 1
0 0
(The 1 is a tie, any of 012 are fine)

0 1 2 1 2 1
2 2 1 0 2 2
2 1 2 0 1 0
0 0 1 0 3 2
3 0 2 0 3 1
1 0 3 2 0 1, 
2 =>
2 1 2
0 0 3
0 2 1
(The 3 is a tie, any of 0123 are fine)

Meta

  • Title help needed
  • Tags are - anything else?
  • Any clarifications?
  • Is this a dupe?
  • Can I have some context?
\$\endgroup\$
0
\$\begingroup\$

Implement OADD_MONTHS

Introduction

The concept of a function to add months to a date, without overflowing if we reach the end of the month, is implemented in many languages/packages. In Teradata SQL it's ADD_MONTHS, here are some examples:

ADD_MONTHS('2021-01-31', 1)   => 2021-02-28
ADD_MONTHS('2021-01-30', 1)   => 2021-02-28
ADD_MONTHS('2021-02-28', 1)   => 2021-03-28
ADD_MONTHS('2021-02-28', -12) => 2020-02-28

However, Teradata SQL has a function that goes a step further, namely OADD_MONTHS. The behaviour of this one is similar, but when given an end-of-month date, it always returns an end-of-month date.
To illustrate the difference:

ADD_MONTHS('2021-02-28', 1)  => 2020-03-28
OADD_MONTHS('2021-02-28', 1) => 2020-03-31

The task

You are given as input:

  • a date D in any reasonable format (including your language's native date/datetime type, a string, number of days/seconds from a fixed point, etc.),
  • an integer n (positive/negative/0).

You should output:

  • a date n months apart from D,
  • if the month n months apart from D has fewer days then the day-of-month of D, output the end of that month,
  • if D is an end-of-month date, output the end of the month.

Any reasonable output form is acceptable (including your language's native date/datetime type, a string, number of days/seconds from a fixed point, etc.)

You may assume the input and target dates are after 0001-01-01 and the date is well defined (so no 2021-03-32).

If you have a builtin specifically for this, consider including a non-builtin answer as well.

Test cases

D, n             => output
2021-01-31, 1    => 2021-02-28
2021-01-30, -1   => 2020-12-30
2021-01-01, -11  => 2020-02-01
2021-02-28, 1    => 2021-03-31
2021-02-28, -12  => 2020-02-29

Meta

  • do we have something similar already?
  • do I need to clarify the task more/less?
\$\endgroup\$
0
\$\begingroup\$

Reveal by Quarters (in need of a better name)

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

A valid answer:

  • Takes a number \$w\$ and a coordinate pair \$(x, y)\$.
  • Outputs a two-dimensional integer array with a width and height of \$2^w\$.
  • This array is initially filled with zeroes.
  • For each number \$n\$ up to \$w\$, increment all of the elements in the subarray of the array split into \$2^n\$ by \$2^n\$ squares that the coordinate pair is inside of.
  • Return this array.

Examples

(with coordinates from top left, 0 indexed, x then y, but your answer may have change these)

w=3, coords=(1,1)
22110000
23110000
11110000
11110000
00000000
00000000
00000000
00000000

w=2, coords=(2,1)
0011
0021
0000
0000

Meta questions

  • Are these tags fitting?
  • Would this be better in one dimension? (like \$3, 2\$ returns 11320000)
  • Should \$w\$ or \$2^w\$ be the input?
  • Is this a duplicate?
\$\endgroup\$
-1
\$\begingroup\$

The only differences that matter

Cops' task

Write two programs (or functions) A and B in the same version of the same programming language. They also should be called in the same way, meaning you can't write one program and one function. Each should accept an integer n and output the term n of a different integer sequence on OEIS.

You should reveal a substring of each of A and B. Call them PA and PB. If one instance of PA is replaced by PB from A, it should become B. That means every byte except the reveal part in A and B should be exactly the same. You also reveal the lengths of A and B, and the two OEIS sequences. You don't reveal the programming language you use.

Your answer is cracked if a robber finds two programs A' and B' that also print the elements in the two integer sequences respectively, where A' is no longer than A, and A' with one instance of PA replaced by PB is also B'. They don't have to be the same with your original A and B. And they don't have to be in the same programming language as yours, as long as they are in the same programming language themselves.

If your answer isn't cracked 7 days after you post the answer, you can reveal your language and the original A and B and mark the answer safe, and it will be immune to future crack. Your answer can still be cracked if you don't do it.

Your score is max(len(A)+len(PA)*5, len(B)+len(PB)*5). The safe answer posted before a certain date with the minimum score wins.

For example, if your two programs are The first program and The second program, you can reveal first and second. Your score is 18 + 6*5 = 48. And a robber can crack your answer by <<first>> <<second>> if they work. But you can also reveal first pro and second pro to prevent this crack.

Please post your answer using this template:

# <length of PA> / <length of A> bytes, <length of PB> / <length of B> bytes, score <score>, <open / safe / cracked>

Part of program A (outputing [<OEIS number>](<OEIS link>)):

    <code of PA>

Part of program B (outputing [<OEIS number>](<OEIS link>)):

    <code of PB>

<any other explanations>

Robbers' task

(To do.)

\$\endgroup\$
9
  • \$\begingroup\$ Do robbers have to produce the same program, or any program? \$\endgroup\$ – Nathan Merrill Oct 28 '16 at 14:47
  • \$\begingroup\$ There are two tricky edge cases around character encodings which the question needs to address. 1. It talks about substrings of A and B, saying that every byte except the revealed ones must be the same. If A and B differ in one Unicode codepoint, such that in UTF-8 they differ in only one byte but it's part of a three-byte sequence, can I post just that one byte as PA/PB or must I post the three-byte sequence? (I.e. are the substrings operating on the bytes or on the codepoints?) \$\endgroup\$ – Peter Taylor Oct 28 '16 at 20:57
  • \$\begingroup\$ 2. If my program is in APL using an 8-bit encoding, do robbers answering in a language other than APL have to have the same bytes in the part of their file corresponding to PA/PB or the same Unicode codepoints? \$\endgroup\$ – Peter Taylor Oct 28 '16 at 20:57
  • \$\begingroup\$ @NathanMerrill Any program. \$\endgroup\$ – jimmy23013 Oct 28 '16 at 21:05
  • \$\begingroup\$ @PeterTaylor I'm considering requiring every program to be in printable ASCII (and tabs and newlines), as some special characters effectively banned many languages. But I'm not sure about newlines, which have the \r problem. \$\endgroup\$ – jimmy23013 Oct 28 '16 at 21:09
  • \$\begingroup\$ Maybe I'll just say \r\n is counted one byte in this challenge, and is interchangeable with \n. But the programs in one submission must use only \n or only \r\n. \$\endgroup\$ – jimmy23013 Oct 28 '16 at 21:13
  • \$\begingroup\$ An example would make this easier to understand, \$\endgroup\$ – xnor Oct 29 '16 at 6:08
  • 2
    \$\begingroup\$ I'm skeptical about having the programming language be a free variable. If a cop writes an answer using a verbose language, a robber can comment out all the visible parts and stuff a terse language answer into the cracks. \$\endgroup\$ – feersum Oct 29 '16 at 11:24
  • \$\begingroup\$ @feersum But that's the whole point of all the requirements. If you comment out all the visible parts, both your programs usually should output the same thing. But I realized it's easy to have some workarounds in languages such as Befunge. I may try to find a way to ban them, or just abandon this post. \$\endgroup\$ – jimmy23013 Oct 31 '16 at 0:59
-1
\$\begingroup\$

Translation Polyglot

Your task is to write a program which runs in two distinct programming languages to translate text. Input should be translated between each language i.e. running your code in Code Language A translates from language 1 to 2, while running your code in Code Language B translates from language 2 to 1.

Rules:

  • Code Languages must be distinct, two versions of the same language are disallowed
  • Your code may be a full program or function
  • Your code must take one string (or nearest equivalent) as input. Input may be user input, function arguments, or other reasonable form
  • Output may be a function return, output to STDOUT, or other reasonable form. I do not care about trailing newlines or spaces
  • Your code may translate from/to any language on the official language list on Wikipedia. List the languages in your answer
  • To accomplish your goal, you may use prebuilt language tanslation dictionaries such as the ones found here.
  • If you read your dictionary as an external file, only the code to read in the file (f = open("dictionary.txt", 'r') in Python) counts towards your byte count. If your dictionary is hardcoded in, only count the bytes required to make it syntatically valid code (s="word1_in_english word1_in_french ..." would be 4 (s="")). Essentially, do not include the dictionary as part of your submissions byte count.
  • The dictionary you use must have been created before this post (including sandbox time). You may not modifiy the dictionary in any way.
  • Any built-in translation tools are disallowed. Built-in dictionaries are ok, but whatever code used to import them into your code must be included in the byte count

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

\$\endgroup\$
5
  • \$\begingroup\$ wait... Are you actually asking for machine translation? Seems very difficult. Haven't you ever seen bad translator? If it actually is machine translation, this won't work, because of the different resolution of the languages (like converting a jpg to a png and expecting the same quality back) \$\endgroup\$ – Destructible Lemon Nov 1 '16 at 4:11
  • \$\begingroup\$ It's really just value lookup. I'm not asking people to to make their own dictionary, just use a pre-built and accept whatever it translates \$\endgroup\$ – wnnmaw Nov 1 '16 at 13:45
  • \$\begingroup\$ But that doesn't really satisfy Language A produces output O from input I, while running in Language B produces output I from input O. \$\endgroup\$ – Destructible Lemon Nov 1 '16 at 22:04
  • \$\begingroup\$ Ah, now I see the source of confusion. Updated text to require basic translation, not symmetric translation \$\endgroup\$ – wnnmaw Nov 2 '16 at 11:53
  • \$\begingroup\$ Also I don't think translation is objective enough for code golf... \$\endgroup\$ – Destructible Lemon Nov 3 '16 at 5:30
-1
\$\begingroup\$

What in the heck just happened?

I want you to write a program that will bleep out the H-word, regardless of where it occurs, whether it is inside of another word or a stand-alone word, whether capitalized or not.

Input and Output

The inputs and outputs of your program may be any of the following: an array of characters, a string, or any other standard data structure which does the job. However, the output must match the case of the input.

Samples:

In the format of Input: Output
A Shell gas station : A Sheck gas station
Hell is a very bad place to be. : Heck is a very bad place to be.
Ella fell and Nelly dug a well. : Ella fell and Nelly dug a well.
Chellsea Thell bought shells. : Checksea Theck bought shecks.

Standard loopholes apply, and the entry submitted by [insert date here] with the lowest number of bytes as defined by the Meta will win.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I can't say for sure, as I don't have an exact reference, but I'm pretty sure a simple find and replace challenge has been done before. \$\endgroup\$ – ATaco Feb 13 '17 at 0:19
  • 2
    \$\begingroup\$ "Hell" and "heck" are both "H-words", so you need to be clearer. Also, I feel like this is a duplicate. Though these are milder swear words, I think someone did one with swear words in general and it got deleted. If you're going to make a find/replace challenge, it's simple enough to make it about something else. \$\endgroup\$ – mbomb007 Feb 13 '17 at 0:19
  • \$\begingroup\$ Ah, I see. So, are you saying I should change what's being replaced or what my idea is? \$\endgroup\$ – Drew Christensen Feb 14 '17 at 0:50
-1
\$\begingroup\$

The 2017 Loader contest

Here's a thing: Let's do the bignum bakeoff again.

Because why not.

What to do

Write a program in less than 256 characters that outputs the biggest number you can.
Yep, that's it. Biggest return value wins.

We'll run the program on a VM with infinite memory. (How do we do this?)

Rules

  • 256 chars max, excluding whitespace
  • Different leagues for each language
  • Output however you want
    • No explicitly printing numbers until your loop runs out. Print the number you generate directly. {1}
  • Program must terminate
  • No implementation-dependent shenanigans.
  • Implementation-independent shenanigans is encouraged.
  • ints are infinite.
  • Program must return the same number every time
  • Submission must include the approximate return value in any suitable googological notation.
  • Whitespace is space, tab, newline, formfeed, and return
    • BrainF***: Whitespace is all non-[]+-<> characters

{1} Allowed ways to return: printf("%d", num); return num;, etc.
Banned ways to return: for(;num>0;num--)printf("99999");, etc.


This is not a dupe of...

This because you can put any characters you want, not just non-digits; because we're hard-limiting the characters.


Suggested rules

  • No floats: float double long double, etc
  • No strings or chars
  • No bitfeilds
  • No looking at Command-line args

Next year's contest will be named after this year's winner, for no particular reason.

http://djm.cc/bignum-rules-posted.txt


Sandbox

  • How do you even test these programs?
  • What other rules should we have?
\$\endgroup\$
9
  • \$\begingroup\$ You don't actually explain the rules of the challenge, we would have to go to that link to find out what we are supposed to do. Aside from that, I think this has a lot of problems with your typing restrictions if these are not limited to C, but limiting it to C wouldn't really fit the spirit of the site. I think you may want to rethink how you want to approach this question. \$\endgroup\$ – FryAmTheEggman May 29 '17 at 16:43
  • \$\begingroup\$ @FryAmTheEggman "Typing restrictions"? (Added proper instructions) \$\endgroup\$ – SIGSTACKFAULT May 29 '17 at 16:45
  • \$\begingroup\$ Your post doesn't describe how people win. Is it by the largest possible number? Anyway, the problems are things like not counting whitespace, which can easily result in degenerate answers, as well as things like I/O streams and whatnot. All of your extra rules seem entirely based around C with no regard for other languages, which will not go well. \$\endgroup\$ – FryAmTheEggman May 29 '17 at 16:48
  • 4
    \$\begingroup\$ In answer to "Because why not": because it will be closed as a dupe. \$\endgroup\$ – Peter Taylor May 29 '17 at 17:59
  • \$\begingroup\$ Here's a couple of rules I would consider. 1. Program must generate the same result every time (e.g. not based on timer, probability, or the like). 2. Submissions should include, if not the exact resulting number, at least a best estimate, in scientific notation if need be. \$\endgroup\$ – Computronium May 30 '17 at 18:32
  • \$\begingroup\$ Scientific notation? People will post answers that far, far exceed that. In fact, Mathematica, 22: Fold[Power,2~Range~9999] It's 2^3^4^...^9999. That's not being represented anytime soon. \$\endgroup\$ – CalculatorFeline May 31 '17 at 3:31
  • 1
    \$\begingroup\$ This is a duplicate, and is also going to come down a lot to whether or not you allow programs that exceed the computational capacity of any existing computer. (If you require programs to work on a physical computer, the best they can possibly do is to use the entirety of memory as a counter and print out 9s over and over again. If you don't, the answers can easily be large enough that you need to use notation invented specifically for describing the number, because all other notations are not enough.) \$\endgroup\$ – user62131 May 31 '17 at 22:40
  • \$\begingroup\$ If your code can simulate a Turing machine, it becomes hard to judge who the winner is, and whether an answer is valid at all. \$\endgroup\$ – anatolyg Jun 1 '17 at 20:35
  • \$\begingroup\$ Re your latest edit: you're wrong. The question it's a dupe of also has a hard limit to the number of characters; in fact it's a harder one, but the best answers could be copied with slight tweaking to take advantage of the extra space. And the digit restriction turned out not to be a serious problem: the winning answer would gain extremely little from being able to use digits. \$\endgroup\$ – Peter Taylor Jun 2 '17 at 9:07
-1
\$\begingroup\$

Golf Cubically code

Your task is to optimize Cubically source code using one or more optimizations in this post.

How this challenge works:

  • You will choose one or more optimizations below and write a program (in the language of your choice) that performs those optimizations on a Cubically program.
  • Your program will take a Cubically program as input using any allowed input methods, and output a Cubically program using any allowed output methods.
  • The first answer to successfully perform all optimizations wins!

Optimizations

1. Face turn arguments

Before a face turn is performed, the interpreter calculates turns = turns mod 4. So R5 would be equivalent to R1 which is equivalent to R, R7 is equivalent to R3 which is equivalent to R', etc. Also note that R11111 is equivalent to R5, and R22 is equivalent to nothing at all.

Performing this optimization will mean evaluating all arguments to an R, L, U, D, M, E, or S command and shortening them as much as possible.

Test cases:

Relevant code -> Optimization
R11           -> R2
R1            -> R
L33           -> L2
U22           ->
D222          -> D2
M11111        -> M
E00001        -> E
S9            -> S

2. Repeated face turn

When multiple calls to the same face turn command are present right next to each other, they can clearly be golfed. For example, R2R1 is equivalent to R3. UUU is equivalent to U3. F2F2F2F2 is equivalent F8.

Test cases:

Relevant code -> optimization
R2R2R2        -> R6            (R2 if you also choose optimization 1)
LLL           -> L3
UU            -> UU or U2
D3D2D1        -> D6            (D2 if you also choose optimization 1)

3. "Set notepad to" commands

There are some commands that, instead of adding to/subtracting from/multiplying by/dividing by the notepad, just assign to it. Here are all such commands:

_^=<>⊕«»·|:

When called with multiple arguments, since each argument calls the command separately, only the final argument is relevant. So =123 is equivalent to =3, _00000 is equivalent to _0, and :12345678987654321 is equivalent to 1.

Test cases:

Relevant code -> Optimization
_333          -> _3
=12321        -> =1
+54321        -> +54321
:55           -> :5
/55           -> /55

4. Repeated non-face-turn commands

When multiple face turn commands are present right by each other, their arguments can simply be added together. Commands do not act this way. While R2 calls R with 2, =2 calls = with the face sum of the front face (face index 2).

To perform this optimization, when multiple commands outside of RLUDFBMES appear next to each other, simply remove the duplicated commands without removing the arguments.

Relevant code -> Optimization
_1_1_1_1      -> _1111         (_1 if you also choose optimization 3)
%11%22%33     -> %112233       (%3 if you also choose optimization 3)
+12345+67+8   -> +12345678

5. Nonexistent commands

Go check out the Cubically commands page and you'll see that there are plenty of characters that are not commands. For example, there are no commands that are lowercase letters.

To perform this optimization, remove all nonexistent commands and their arguments from the Cubically source. If the commands also have arguments, you must remove the arguments so that they are not passed to the previous command.

Test cases:

Relevant code -> Optimization
moo cow moo   -> 
moo2cow2moo   -> 
misteR2 FOO   -> R2F
FEAR ME.      -> ERME
u1U2u3U4u5U6  -> U2U4U6   (nothing if you also choose optimization 1, U12 if you also choose optimization 2)

6. Non-implicit commands

There are lots of implicit commands in Cubically (RLUDFBMES()$~&E!), but there are plenty that need to be called with arguments. So %%%% is equivalent to nothing at all while %%2%% is equivalent to %2.

Test cases:

Relevant code -> Optimization
%%%%          -> 
$$$$          -> $$$$
++2++2++2     -> +2+2+2                 (+222 if you also choose optimization 4)
+++>--<-      -> Not Brainf**k, sorry!  (:P)

Sandbox

I'll add more optimizations later.

\$\endgroup\$
2
  • \$\begingroup\$ Clarification on R123: That's the same as R6 and R2, not R3, right? Digits are summed, there are multidigit numbers? That would be better to specify \$\endgroup\$ – isaacg Aug 17 '17 at 20:13
  • \$\begingroup\$ A few things: first, I can't find the tag "fgitw", is there a typo? Second, does optimization 1 require handling F and B as well, or just the currently listed ones? Third, in optimization 3 most of the listed commands seem invalid because the notepad is used in calculation and then overwritten with the output; for example =11 is not the same as =1 in most circumstances. In fact, I think only _: are valid. Fourth, is the winning answer one which performs all optimizations in a single program, or one which contains a separate program for each optimization? \$\endgroup\$ – Kamil Drakari Aug 18 '17 at 18:03
-1
\$\begingroup\$

Proper Kerning

Kerning is the adjustment of spacing between pairs of letters in order to obtain an aesthetic result. When kerning is applied automatically by a program (typically whatever editor you're using), it is said to be automatic. There are two types of automatic kerning. The one used in this challenge is metric kerning. With metric kerning, the amount of space between pairs of letters is dictated by the kerning tables found in the font file.

Given a TrueType font file, output the kerning values for each mapping in the kerning table for ASCII characters 48 - 122 inclusive.

Example

calibri.ttf

l="A" r="C" v="-15"
l="A" r="G" v="-15"
l="A" r="J" v="23"
l="A" r="O" v="-23"
l="A" r="Q" v="-23"
l="A" r="T" v="-160"
l="A" r="U" v="-32"
l="A" r="V" v="-89"
l="A" r="W" v="-80"
l="A" r="Y" v="-150"
l="A" r="t" v="-52"
l="A" r="v" v="-38"
l="A" r="y" v="-41"
l="A" r="?" v="-68"
l="B" r="A" v="-20"
l="B" r="T" v="-48"
l="B" r="V" v="-25"
l="B" r="W" v="-24"
l="B" r="X" v="-44"
l="B" r="Y" v="-57"
l="B" r="Z" v="-20"
l="B" r="f" v="-20"
l="B" r="t" v="-20"
l="B" r="v" v="-20"
l="B" r="x" v="-15"
l="B" r="y" v="-20"
l="C" r="G" v="-18"
l="C" r="J" v="12"
l="C" r="O" v="-18"
l="C" r="Q" v="-18"
l="C" r="T" v="10"
l="D" r="A" v="-30"
l="D" r="J" v="-22"
l="D" r="T" v="-23"
l="D" r="V" v="-24"
l="D" r="W" v="-14"
l="D" r="X" v="-31"
l="D" r="Y" v="-39"
l="D" r="Z" v="-22"
l="E" r="A" v="-22"
l="E" r="C" v="-24"
l="E" r="G" v="-24"
l="E" r="O" v="-32"
l="E" r="Q" v="-32"
l="E" r="S" v="-20"
l="E" r="Z" v="-10"
l="E" r="a" v="-34"
l="E" r="c" v="-28"
l="E" r="d" v="-30"
l="E" r="e" v="-37"
l="E" r="f" v="-64"
l="E" r="o" v="-37"
l="E" r="q" v="-30"
l="E" r="t" v="-24"
l="E" r="v" v="-48"
l="E" r="w" v="-34"
l="E" r="y" v="-48"
l="F" r="A" v="-115"
l="F" r="C" v="-18"
l="F" r="G" v="-18"
l="F" r="J" v="-109"
l="F" r="O" v="-18"
l="F" r="Q" v="-18"
l="F" r="S" v="-29"
l="F" r="X" v="-22"
l="F" r="Z" v="-11"
l="F" r="a" v="-55"
l="F" r="c" v="-28"
l="F" r="d" v="-20"
l="F" r="e" v="-30"
l="F" r="o" v="-28"
l="F" r="q" v="-20"
l="F" r="s" v="-35"
l="G" r="T" v="-10"
l="G" r="V" v="-10"
l="G" r="W" v="-9"
l="G" r="Y" v="-30"
l="G" r="v" v="-29"
l="G" r="w" v="-22"
l="G" r="x" v="-14"
l="G" r="y" v="-30"
l="J" r="A" v="-35"
l="J" r="X" v="-20"
l="K" r="C" v="-78"
l="K" r="G" v="-80"
l="K" r="O" v="-97"
l="K" r="Q" v="-97"
l="K" r="S" v="-18"
l="K" r="U" v="-29"
l="K" r="W" v="-34"
l="K" r="a" v="-34"
l="K" r="c" v="-40"
l="K" r="d" v="-33"
l="K" r="e" v="-37"
l="K" r="f" v="-25"
l="K" r="m" v="-32"
l="K" r="n" v="-32"
l="K" r="o" v="-37"
l="K" r="p" v="-32"
l="K" r="q" v="-33"
l="K" r="r" v="-32"
l="K" r="s" v="-18"
l="K" r="t" v="-38"
l="K" r="u" v="-32"
l="K" r="v" v="-101"
l="K" r="w" v="-95"
l="K" r="y" v="-85"
l="L" r="C" v="-22"
l="L" r="G" v="-47"
l="L" r="J" v="25"
l="L" r="O" v="-45"
l="L" r="Q" v="-45"
l="L" r="T" v="-150"
l="L" r="U" v="-44"
l="L" r="V" v="-147"
l="L" r="W" v="-118"
l="L" r="Y" v="-167"
l="L" r="f" v="-23"
l="L" r="t" v="-38"
l="L" r="v" v="-78"
l="L" r="w" v="-72"
l="L" r="y" v="-79"
l="O" r="A" v="-23"
l="O" r="J" v="-27"
l="O" r="T" v="-55"
l="O" r="V" v="-25"
l="O" r="W" v="-22"
l="O" r="X" v="-64"
l="O" r="Y" v="-55"
l="O" r="Z" v="-38"
l="O" r="x" v="-12"
l="O" r="z" v="-10"
l="P" r="A" v="-151"
l="P" r="J" v="-140"
l="P" r="T" v="-9"
l="P" r="V" v="-10"
l="P" r="X" v="-35"
l="P" r="Y" v="-11"
l="P" r="Z" v="-29"
l="P" r="a" v="-44"
l="P" r="c" v="-43"
l="P" r="d" v="-34"
l="P" r="e" v="-41"
l="P" r="f" v="12"
l="P" r="o" v="-41"
l="P" r="q" v="-34"
l="P" r="s" v="-32"
l="P" r="t" v="12"
l="P" r="y" v="12"
l="Q" r="J" v="41"
l="Q" r="T" v="-47"
l="Q" r="V" v="-25"
l="Q" r="W" v="-12"
l="Q" r="X" v="12"
l="Q" r="Y" v="-46"
l="Q" r="g" v="59"
l="Q" r="j" v="79"
l="Q" r="x" v="31"
l="Q" r=";" v="60"
l="Q" r="]" v="32"
l="R" r="C" v="-18"
l="R" r="G" v="-19"
l="R" r="O" v="-20"
l="R" r="Q" v="-20"
l="R" r="S" v="-27"
l="R" r="T" v="-20"
l="R" r="V" v="-28"
l="R" r="W" v="-18"
l="R" r="Y" v="-30"
l="R" r="e" v="-36"
l="R" r="o" v="-42"
l="R" r="v" v="-26"
l="R" r="w" v="-33"
l="R" r="y" v="-33"
l="S" r="A" v="-15"
l="S" r="J" v="-9"
l="S" r="T" v="-14"
l="S" r="V" v="-14"
l="S" r="W" v="-15"
l="S" r="X" v="-13"
l="S" r="Y" v="-20"
l="S" r="v" v="-23"
l="S" r="w" v="-17"
l="S" r="y" v="-25"
l="T" r="A" v="-160"
l="T" r="C" v="-42"
l="T" r="G" v="-59"
l="T" r="J" v="-65"
l="T" r="O" v="-58"
l="T" r="Q" v="-58"
l="T" r="S" v="-10"
l="T" r="T" v="28"
l="T" r="a" v="-160"
l="T" r="c" v="-177"
l="T" r="d" v="-147"
l="T" r="e" v="-182"
l="T" r="g" v="-151"
l="T" r="m" v="-127"
l="T" r="n" v="-127"
l="T" r="o" v="-182"
l="T" r="p" v="-127"
l="T" r="q" v="-147"
l="T" r="r" v="-127"
l="T" r="s" v="-153"
l="T" r="u" v="-127"
l="T" r="v" v="-92"
l="T" r="w" v="-86"
l="T" r="x" v="-90"
l="T" r="y" v="-93"
l="T" r="z" v="-142"
l="T" r=";" v="-114"
l="T" r=":" v="-134"
l="U" r="A" v="-45"
l="U" r="J" v="-40"
l="V" r="A" v="-96"
l="V" r="C" v="-18"
l="V" r="G" v="-25"
l="V" r="J" v="-80"
l="V" r="O" v="-27"
l="V" r="Q" v="-27"
l="V" r="S" v="-12"
l="V" r="V" v="9"
l="V" r="a" v="-114"
l="V" r="c" v="-103"
l="V" r="d" v="-87"
l="V" r="e" v="-102"
l="V" r="g" v="-100"
l="V" r="m" v="-50"
l="V" r="n" v="-50"
l="V" r="o" v="-86"
l="V" r="p" v="-50"
l="V" r="q" v="-87"
l="V" r="r" v="-50"
l="V" r="s" v="-90"
l="V" r="u" v="-50"
l="V" r="y" v="-35"
l="V" r="z" v="-82"
l="V" r=";" v="-108"
l="V" r=":" v="-73"
l="W" r="A" v="-93"
l="W" r="C" v="-22"
l="W" r="G" v="-22"
l="W" r="J" v="-88"
l="W" r="O" v="-22"
l="W" r="Q" v="-22"
l="W" r="S" v="-10"
l="W" r="X" v="-13"
l="W" r="a" v="-71"
l="W" r="c" v="-78"
l="W" r="d" v="-72"
l="W" r="e" v="-75"
l="W" r="g" v="-54"
l="W" r="m" v="-60"
l="W" r="n" v="-60"
l="W" r="o" v="-86"
l="W" r="p" v="-60"
l="W" r="q" v="-72"
l="W" r="r" v="-60"
l="W" r="s" v="-73"
l="W" r="u" v="-60"
l="W" r="v" v="-34"
l="W" r="y" v="-53"
l="W" r=";" v="-156"
l="X" r="C" v="-57"
l="X" r="G" v="-65"
l="X" r="O" v="-57"
l="X" r="Q" v="-57"
l="X" r="S" v="-20"
l="X" r="d" v="-44"
l="X" r="e" v="-39"
l="X" r="g" v="-9"
l="X" r="o" v="-38"
l="X" r="q" v="-44"
l="X" r="t" v="-31"
l="X" r="u" v="-38"
l="X" r="v" v="-55"
l="X" r="w" v="-49"
l="X" r="y" v="-43"
l="Y" r="A" v="-152"
l="Y" r="C" v="-67"
l="Y" r="G" v="-67"
l="Y" r="J" v="-112"
l="Y" r="O" v="-66"
l="Y" r="Q" v="-66"
l="Y" r="S" v="-17"
l="Y" r="Z" v="-10"
l="Y" r="a" v="-134"
l="Y" r="c" v="-159"
l="Y" r="d" v="-131"
l="Y" r="e" v="-147"
l="Y" r="f" v="-62"
l="Y" r="g" v="-142"
l="Y" r="i" v="-32"
l="Y" r="j" v="-49"
l="Y" r="m" v="-94"
l="Y" r="n" v="-94"
l="Y" r="o" v="-153"
l="Y" r="p" v="-94"
l="Y" r="q" v="-131"
l="Y" r="r" v="-94"
l="Y" r="s" v="-115"
l="Y" r="t" v="-44"
l="Y" r="u" v="-94"
l="Y" r="v" v="-69"
l="Y" r="w" v="-62"
l="Y" r="x" v="-70"
l="Y" r="y" v="-65"
l="Y" r="z" v="-100"
l="Y" r=";" v="-138"
l="Y" r=":" v="-154"
l="Z" r="A" v="-11"
l="Z" r="C" v="-25"
l="Z" r="G" v="-24"
l="Z" r="O" v="-24"
l="Z" r="Q" v="-24"
l="Z" r="W" v="-7"
l="Z" r="Y" v="-7"
l="Z" r="a" v="-10"
l="Z" r="c" v="-12"
l="Z" r="d" v="-18"
l="Z" r="e" v="-31"
l="Z" r="o" v="-29"
l="Z" r="q" v="-18"
l="Z" r="v" v="-45"
l="Z" r="w" v="-38"
l="Z" r="y" v="-37"
l="a" r="f" v="-12"
l="a" r="t" v="-19"
l="a" r="v" v="-34"
l="a" r="w" v="-14"
l="a" r="x" v="-19"
l="a" r="y" v="-38"
l="b" r="f" v="-17"
l="b" r="s" v="-10"
l="b" r="t" v="-9"
l="b" r="v" v="-10"
l="b" r="w" v="-10"
l="b" r="x" v="-41"
l="b" r="y" v="-10"
l="b" r="z" v="-28"
l="c" r="a" v="-17"
l="c" r="o" v="-17"
l="e" r="f" v="-18"
l="e" r="t" v="-11"
l="e" r="v" v="-10"
l="e" r="w" v="-10"
l="e" r="x" v="-31"
l="e" r="y" v="-13"
l="e" r="z" v="-20"
l="f" r="a" v="-40"
l="f" r="c" v="-45"
l="f" r="d" v="-53"
l="f" r="e" v="-51"
l="f" r="f" v="-20"
l="f" r="g" v="-60"
l="f" r="o" v="-43"
l="f" r="q" v="-53"
l="f" r="s" v="-27"
l="f" r="v" v="13"
l="f" r="w" v="6"
l="f" r="y" v="10"
l="f" r="z" v="-20"
l="g" r="a" v="-38"
l="g" r="c" v="-12"
l="g" r="d" v="-19"
l="g" r="e" v="-17"
l="g" r="g" v="19"
l="g" r="o" v="-14"
l="g" r="q" v="-19"
l="g" r="t" v="-31"
l="h" r="f" v="-12"
l="h" r="t" v="-19"
l="h" r="v" v="-34"
l="h" r="w" v="-14"
l="h" r="x" v="-19"
l="h" r="y" v="-38"
l="k" r="a" v="-35"
l="k" r="c" v="-48"
l="k" r="d" v="-56"
l="k" r="e" v="-66"
l="k" r="o" v="-69"
l="k" r="q" v="-56"
l="k" r="s" v="-19"
l="k" r="t" v="-10"
l="k" r="u" v="-26"
l="m" r="f" v="-12"
l="m" r="t" v="-19"
l="m" r="v" v="-34"
l="m" r="w" v="-14"
l="m" r="x" v="-19"
l="m" r="y" v="-38"
l="n" r="f" v="-12"
l="n" r="t" v="-19"
l="n" r="v" v="-34"
l="n" r="w" v="-14"
l="n" r="x" v="-19"
l="n" r="y" v="-38"
l="o" r="v" v="-9"
l="o" r="w" v="-8"
l="o" r="x" v="-40"
l="o" r="y" v="-11"
l="o" r="z" v="-27"
l="p" r="f" v="-17"
l="p" r="s" v="-10"
l="p" r="t" v="-9"
l="p" r="v" v="-10"
l="p" r="w" v="-10"
l="p" r="x" v="-41"
l="p" r="y" v="-10"
l="p" r="z" v="-28"
l="q" r="g" v="10"
l="r" r="a" v="-42"
l="r" r="c" v="-30"
l="r" r="d" v="-28"
l="r" r="e" v="-27"
l="r" r="g" v="-28"
l="r" r="o" v="-33"
l="r" r="q" v="-28"
l="r" r="s" v="-35"
l="r" r="v" v="19"
l="r" r="w" v="11"
l="r" r="y" v="10"
l="s" r="f" v="-19"
l="s" r="t" v="-23"
l="s" r="v" v="-31"
l="s" r="w" v="-10"
l="s" r="x" v="-22"
l="s" r="y" v="-37"
l="s" r="z" v="-18"
l="t" r="a" v="-25"
l="t" r="c" v="-25"
l="t" r="d" v="-23"
l="t" r="e" v="-22"
l="t" r="o" v="-20"
l="t" r="q" v="-23"
l="t" r="t" v="-29"
l="v" r="a" v="-30"
l="v" r="c" v="-25"
l="v" r="d" v="-20"
l="v" r="e" v="-20"
l="v" r="f" v="11"
l="v" r="g" v="-28"
l="v" r="o" v="-19"
l="v" r="q" v="-20"
l="v" r="s" v="-9"
l="v" r="t" v="10"
l="v" r="v" v="12"
l="v" r="w" v="12"
l="v" r="y" v="12"
l="v" r="z" v="-26"
l="w" r="a" v="-23"
l="w" r="c" v="-20"
l="w" r="d" v="-18"
l="w" r="e" v="-18"
l="w" r="f" v="6"
l="w" r="g" v="-18"
l="w" r="o" v="-19"
l="w" r="q" v="-18"
l="w" r="s" v="-18"
l="w" r="t" v="4"
l="w" r="v" v="12"
l="w" r="w" v="8"
l="w" r="y" v="12"
l="w" r="z" v="-17"
l="x" r="a" v="-37"
l="x" r="c" v="-46"
l="x" r="d" v="-44"
l="x" r="e" v="-54"
l="x" r="o" v="-55"
l="x" r="q" v="-44"
l="x" r="s" v="-12"
l="x" r="t" v="6"
l="x" r="u" v="-20"
l="y" r="a" v="-31"
l="y" r="c" v="-26"
l="y" r="d" v="-24"
l="y" r="e" v="-25"
l="y" r="f" v="10"
l="y" r="g" v="-26"
l="y" r="o" v="-24"
l="y" r="q" v="-24"
l="y" r="s" v="-19"
l="y" r="t" v="10"
l="y" r="v" v="12"
l="y" r="w" v="8"
l="y" r="y" v="10"
l="y" r="z" v="-17"
l="z" r="a" v="-34"
l="z" r="c" v="-45"
l="z" r="d" v="-46"
l="z" r="e" v="-46"
l="z" r="f" v="-10"
l="z" r="g" v="-17"
l="z" r="o" v="-45"
l="z" r="q" v="-46"
l="z" r="s" v="-22"
l="z" r="u" v="-10"
l="z" r="v" v="-18"
l="z" r="w" v="-22"
l="z" r="y" v="-18"

Scoring

This is , so the shortest answer (in bytes) wins.

Meta

I know this challenge is going to need a lot of work before it's ready for main. Please hold criticisms for now. Helpful ideas and thoughts are welcome.

\$\endgroup\$
7
  • \$\begingroup\$ I'm not sure that the problem is well defined. There's a reason it's called font hinting: the rendering application is free to take it into account or not, or even to apply more complex logic. E.g. some fonts have multiple sets of font hints for different contexts. There are other complex issues. A font can have Latin and Cyrillic letters and define hints for kerning between pairs of Latin and pairs of Cyrillic but not between Latin and Cyrillic; however, some letters may have identical glyphs, so a judgement on whether the kerning is "correct" might be ambiguous. Then there's antialiasing. \$\endgroup\$ – Peter Taylor May 24 '17 at 6:15
  • \$\begingroup\$ @PeterTaylor Good notes. I will likely restrict the character set. I just wanted to start getting ideas down in the sandbox. \$\endgroup\$ – Poke May 24 '17 at 6:51
  • \$\begingroup\$ Very ambiguous. \$\endgroup\$ – anna328p May 25 '17 at 17:48
  • \$\begingroup\$ @Mendeleev It's not done yet. I'm aware it's ambiguous. \$\endgroup\$ – Poke May 26 '17 at 16:10
  • \$\begingroup\$ Looking at developer.apple.com/fonts/TrueType-Reference-Manual/RM06/… I can see a number of issues to address. 16- vs 32-bit entries? Should multiple tables be combined or printed separately? All tables or only tables with certain coverage values? Which of the four defined formats need to be supported? Do you have a test case which covers glyph index differing from codepoint? \$\endgroup\$ – Peter Taylor Sep 16 '17 at 17:28
  • \$\begingroup\$ @PeterTaylor I have a proof of concept that I wrote (it's the reason I have taken so long to update this) and I'm planning to address all of your questions. Thanks for doing a bit of research to help me out, though :] \$\endgroup\$ – Poke Sep 16 '17 at 18:57
  • \$\begingroup\$ Downvoter, why? \$\endgroup\$ – Poke Oct 4 '17 at 21:03
-1
\$\begingroup\$

Six Flags over HTTP

Let's say you need to transmit six boolean flags in a URL string. Obviously you could do it with six ones or zeroes, but you want better compression. With a little math you can pack them into two characters using 0-7 octal.

How about mapping all six to a single ASCII character? Here we have a problem: you are not allowed to use , / ? : @ & = + $ # or space. Now the range of printable ASCII no longer has 64 valid characters in a row.

In Javascript (or another language that can run from a web page, if any), what is the shortest code for a pair of functions to encode and decode this data, between an array of six booleans and a single character?

\$\endgroup\$
2
  • \$\begingroup\$ -1 language restriction, most languages have HTTP libraries so I think any language should be allowed \$\endgroup\$ – ASCII-only Sep 24 '17 at 13:11
  • \$\begingroup\$ This challenge could be improved by rephrasing it to: "Write a bijective function between an array of six booleans and a single printable character excluding the characters ,/?:@&=+$# ". Mentioning that the encoder and decoder should be separate programs/functions would be helpful. Also, may the encoder and decoder share code? \$\endgroup\$ – fireflame241 Sep 24 '17 at 22:08
-1
\$\begingroup\$

Count letter frequency

Inspired by question Tweetable hash function challenge, you should take the English dictionary used there and produce a program or function that outputs the the absolute and relative frequency of each character. It is CASE SENSITIVE and the APOSTROPHE is also accountable as a real letter.

Example of a valid output format (but with stupid guessing values):

A      5566    20%
...
Z        60     0.2%
a     27000    30%
...
z       120     0.01%
'       450     3.5%

It is , but no answer will be accepted. Wanna know shortest script for each language.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 (01) Don't rely on another challenge to define yours; include all the information we need in your write-up. (02) Make an effort to come up with some actual test cases - do you honestly expect us to verify our solutions against "stupid guessing values"? \$\endgroup\$ – Shaggy Sep 30 '17 at 0:55
-1
\$\begingroup\$

Is it a perfect loop?

Your task is to take a GIF or an animated image in any reasonable format as input (including taking the file name of a GIF in the current directory), and output whether it is a "perfect loop" - that is, the frames transition seamlessly from the end to the start, and a human cannot notice where it starts and ends at first glance. Return or print a truthy value if it is a perfect loop, otherwise print or return a falsy value.

Scoring

Winners will be determined from the percentage of test cases they get correct. In the event of a tie, highest votes wins. You can view test cases at https://ghostbin.com/paste/m3yaw. Show your score against the test cases when you post.

Input

If you are not taking input in a GIF, please provide a program that will convert a GIF to your desired format.

Images corresponding to a truthy value have been taken from /r/perfectloops and for falsy test cases, /r/almostperfectloops and /r/gifs.

Restrictions

  • Hard coding is not allowed (violates standard loophole 1 and 2).
  • You must provide consistent results for the same GIF (no randomness)
  • Remember, this is not , so byte count is not needed in your solution. Just post the language name and add the percentage correct when I comment.
\$\endgroup\$
2
  • \$\begingroup\$ I'm not sure it's as simple as comparing the first to the last frame, if it is we'd have duplicate frames. is this challenge allowing HTTP requests? \$\endgroup\$ – tuskiomi Oct 17 '17 at 21:15
  • \$\begingroup\$ If hashing the inputs is not allowed, then you should clearly define what constitutes a “perfect loop”. It's not good to extrapolate from a handful of test cases where the pass/fail cases are very similar. \$\endgroup\$ – japh Oct 18 '17 at 14:31
1
97 98
99
100 101
110

You must log in to answer this question.

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