460
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43

2590 Answers 2590

0
\$\begingroup\$

Paint with Pride!

Task: Output a 6 banded version of the pride flag

Details:

The flag consists of 6 bands of colour, each band is rectangular, and all are the same size which is 9x1 units (WxH) . These bands are stacked one on top of each other in the order shown to form a flag that is 9x6 units in size.

The output scale can be chosen by the participant, but all components must be in those ratios, that is, an output must have an aspect ratio which is a multiple of 3:2.

The hexadecimal values and relative positions of the colours are as below:

Full size

Or from top to bottom RGB (255,0,0), (255,153,0), (255,255,0), (0,153,0), (0,0,255), (204,0,153)

A minimal version would look like this:

Min size

Acceptable output:

Output to screen or as a file in a commonly accepted image format is allowed, ascii art is however not.

Sandbox notes:

related, related

I chose this flag because I think the rainbow provides potential for an additional mathematical element

I'm not sure whether to include a minimum size limit, such as the one for drawing the french flag, as perhaps the small output size allows hardcoded answers to succeed (which I don't really want) - any advice?

\$\endgroup\$
  • 1
    \$\begingroup\$ This is a duplicate of this unfortunately \$\endgroup\$ – caird coinheringaahing Aug 29 '17 at 19:05
  • \$\begingroup\$ @cairdcoinheringaahing Shoot, all that time searching for "Pride" and "Flags", forgot to search for rainbow! Perhaps this is significant-enough a variant (rectangle vs bow) that it will allow for different approaches though. I'm not sure what the etiquette is, but I guess I'll leave this up for a while longer and let votes tell me whether it is too much of a duplicate to post. \$\endgroup\$ – Greedo Aug 29 '17 at 19:25
  • \$\begingroup\$ personally, I would close as a duplicate, but if you want to keep it here and see otherwise, go ahead. \$\endgroup\$ – caird coinheringaahing Aug 29 '17 at 19:26
0
\$\begingroup\$

The source of pi

Inspired by an International Obfuscated C Code Contest entry.

Task

As you all know, pi is a constant that represents the ratio of a circle's circumference to its diameter.

Using the dimensions of your own source code, approximate pi to at least two decimal places.

That is, your source code should read itself to obtain both circumference and diameter, then output the ratio.

For example, if your code is:

 AB
CDEF
 GH

Your circumference is 14 and your diameter is 4.

For the purposes of this challenge, let diameter equal the larger of the height or width of your code.

Rules

  • Take no input
  • Hardcoded values for pi are not allowed
  • Output pi to at least two decimal places (e.g., 3.14 and 3.1415 are both acceptable outputs)
  • Answers can be either whole programs or functions

Notes

Answers with higher precision values are acceptable.

Standard rules apply.


Meta

Looking for suggestions of a better title.

\$\endgroup\$
  • 1
    \$\begingroup\$ Well, I'm not sure what "Using the area of your own source code" means. I could do some pretty "standard" approximation algorithm to fullfill your rules. \$\endgroup\$ – Felix Palmen Aug 29 '17 at 16:58
  • \$\begingroup\$ Wouldn't print(3.14) work? It isn't hardcoding pi, as pi isn't 3.14. \$\endgroup\$ – caird coinheringaahing Aug 29 '17 at 19:22
  • \$\begingroup\$ @FelixPalmen - I've updated the specification. Hopefully it is more clear. \$\endgroup\$ – CzarMatt Aug 29 '17 at 20:14
  • \$\begingroup\$ @cairdcoinheringaahing - I've updated the specification. Hopefully it is more clear. \$\endgroup\$ – CzarMatt Aug 29 '17 at 20:16
0
\$\begingroup\$

"Square Root of Pi(e)"

A pie (r=3) is drawn as such:

  @@
 @@@@
@@@@@@
 @@@@
  @@

Pretending that it's a perfect circle, the square root of such a pie would be sqrt(PI*32) = 3sqrt(PI) ~ 5.317. Now take a square out of the pie, whose area is closest to the square root of the pie. In this case it would be a square of area 4. Therefore, you can output:

  @@
 @@@@
@@  @@
 @  @
  @@

Yep, I took a square out of the pie, how do you like that?


r=7

      @@
     @@@@
    @@@@@@
   @@@@@@@@
  @@@@@@@@@@ 
 @@@@@@@@@@@@
@@@@@@@@@@@@@@
 @@@@@@@@@@@@
  @@@@@@@@@@
   @@@@@@@@
    @@@@@@
     @@@@
      @@ 

7*sqrt(PI) ~ 12.407. Closer to 3x3 than 4x4 square.

      @@
     @@@@
    @@@@@@
   @@@@@@@@
  @@@@@@@@@@ 
 @@@@@@@@@@@@
@@@@@@@@@@@@@@
 @@@@@@   @@@
  @@@@@   @@
   @@@@   @
    @@@@@@
     @@@@
      @@ 

Specifications:

  1. Input will be only a "pie" with integer radius of at least two. As you can see, the longest row has 2r @s, and the smallest rows have 2 @s.
  2. You can use a symbol other than "@".
  3. You can take a square out of the inside or the edge.
  4. Approximate PI to at least 3.14.

Bonus: Valid answers that are in a language with food-related name get a free upvote!

\$\endgroup\$
  • \$\begingroup\$ You don't ever define How one forms the pie shape, and in general you seem to be lacking specification. \$\endgroup\$ – Wheat Wizard Sep 3 '17 at 3:37
0
\$\begingroup\$

The Best Question

This site gets a variety of questions: the good, the bad, the ugly. However, I've noticed some patterns that I think will help us find The Best Question (of a given week).

Procedure

You are given a date in a human-readable format of your choice as input. You need to find the best question from that week. The week starts on Sunday and ends on Saturday. Click on the link for a valid query to use if the input is Aug 31, 2017. Note that when using the API without a key you can use UNIX epoch time or YYYY-MM-DD to specify the dates (info here). Since this site gets only about 45 questions a week, you can assume that no more than 100 questions will be asked in a given week in order to avoid pagination.

Scoring

First of all, closed questions are disqualified. Next, here is the formula for Question Rating (QR)1, given Question Score (S) and Number of Answers (A):

The thinking is that there are two kinds of questions that undeservedly get a very high question score: 1) the ones that are easy and get a lot of answers, and 2) the ones that are so difficult that they get few or no answers. I've determined that the best questions have a QuestionScore:Answer ratio of about 3:2.

Output

All you have to do is output the full URL of the question that got the best question score. If multiple tie, you can output them all or just one.

Example

Here's a list of 8 imaginary questions, with their question score followed by the number of answers they received, and their resulting QR:

1. +6, 23A -> -0.333
2. +10, 0A -> 7.78
3. +8, 4A -> 7.56
4. -2, 6A -> -4.44
5. +5, 3A [closed] -> DQ
6. +20 2A -> 16.22
7. +24, 40A -> 16
8. +15, 14A -> 13.67

So the winner is question 6. Output its URL.

Note

You don't need to handle the rare edge case when there are no valid questions in a given week.

1Disclaimer: This scoring system is just a joke.


Suggestions on formula and other stuff welcome.

\$\endgroup\$
  • \$\begingroup\$ Is that abs((QuestionScore/2)-Answers)/2 or abs(QuestionScore/(2-Answers))/2? \$\endgroup\$ – Shaggy Sep 1 '17 at 12:05
  • \$\begingroup\$ Hopefully this looks a bit better. \$\endgroup\$ – geokavel Sep 1 '17 at 15:29
0
\$\begingroup\$

Extend the Pattern

Given a raster image with a lattice pattern, extend it to twice the size of the input image in both directions.

Details

The input image is a section of an infinite repeating pattern defined by two vectors u=(ux,uy),v=(vx,vy) with integer entries, that are linearly independent. This means that both vectors are nonzero and do not point in the same direction. The pattern is defined such that the pixel at a point p = (x,y) has the exact same colour as the pixel at

q := p + s*u + t*v 

for every integer s,t. This means if you know the colours of the pixels within the fundamental parallelogram Z = { s*u + t*v | s in [0,1),t in [0,1)} and corresponding vectors u,v you can extend the pattern to an arbitrary size. The goal of this challenge is finding the pattern and extend the image.

enter image description here

Specs

  • You can take the input image in any non-compressed image format that allows for at least 3 colours, this includes e.g. matrices, 2d arrays or strings.
  • The input method must match the output method. That means if you read a .png file as input, you must also write a .png file as output, or if you take the input via console, you must also print the output via console e.t.c.

Examples

(to be added...)

\$\endgroup\$
  • \$\begingroup\$ Is there freedom to choose which quadrant of the output image corresponds to the input image? \$\endgroup\$ – Peter Taylor Sep 3 '17 at 18:05
  • \$\begingroup\$ You need to add some harder test-cases - at present you can just check for overlaps, tile "infinitely" then crop. \$\endgroup\$ – wizzwizz4 Sep 4 '17 at 16:25
  • \$\begingroup\$ @PeterTaylor Good question, I think I will leave the direction arbitrary. \$\endgroup\$ – flawr Sep 4 '17 at 19:53
  • \$\begingroup\$ @wizzwizz4 I think this method works in any case, or do you have an example in mind where this does not work? \$\endgroup\$ – flawr Sep 4 '17 at 19:54
  • \$\begingroup\$ @flawr One where there's less than one copy of the parallelogram... wait, that wouldn't prevent the overlap technique from working. \$\endgroup\$ – wizzwizz4 Sep 4 '17 at 19:58
0
\$\begingroup\$

Golf a Brainfuck compresser.

The eso-lang Brainfuck only has 8 instructions that do something: +-><[],. so in theory you could represent them in 3 bits. You could store 8 instructions in 24 bits or 3 bytes.

BrnFck

This is compressed brainfuck an instruction will be represented by its bits.

  1. + : 000
  2. - : 001
  3. > : 010
  4. < : 011
  5. [ : 100
  6. ] : 101
  7. , : 110
  8. . : 111

This is a language counted in bits, 8 bits is 1 byte depending on the challenge you may round up or keep a decimal.

The goal

Write the shortest program that can compile any inputted brainfuck code to BrnFck code:

  • You can choose how you output it, byte,bit/boolean arrays and output streams are all acceptable. Just printing ASCII-letters is too.
  • You can do anything (including crash) if the input isn't valid code or contains a non-bf character.

And can compile the BrnFck code back to Brainfuck (or any other language (except BrnFck)). You may ask which way you want to compile or write 2 separate programs/functions and sum their scores.

If you post the code online (for example as an answer) this should automatically allow BrnFck as a language in all future challenges!

Scoring

If you use brainfuck you can divide your bytes by 2.

If you use BrnFck you can divide your bytes by 4 (let's get some recursion going here).

1 bit will be counted as 0.125 bytes (please put both in the title) so decimal byte scores are allowed.

Tags

brainfuck,code-golf,...

\$\endgroup\$
  • 1
    \$\begingroup\$ This encoding doesn't really work since no sensible architecture allows partial bits. Since each 3 bit word is already used, there is no way to distinguish say ,+. from ,+.. if you happen to fill the remaining bits in that way. That said, it isn't totally required for the question for this to work. Otherwise, the bonuses and scoring are needless and confusing, so I'd recommend removing them. \$\endgroup\$ – FryAmTheEggman Sep 3 '17 at 16:57
  • 3
    \$\begingroup\$ Nearly every byte score on PPCG is decimal (base 10): I think you mean that fractional byte scores are possible. To deal with the padding problem, I suggest that you specify that where one or two padding bits are required, 0 should be used; and where three to seven are required, the padding should be 101 followed by as many 0s as necessary. Since [] must be balanced, this allows unambiguous detection of the padding on decompression. Then make sure to include a test case which ends in ] and requires no padding... \$\endgroup\$ – Peter Taylor Sep 4 '17 at 8:02
0
\$\begingroup\$

Program that allows the user to edit it's own source code

Write a program that displays and allows the user to view, edit and save it's own source code.

  • If no edits are made, the output file should be the same as the program, and hence executing it should allow the user to edit the program's code again. (ie a quine)
  • If the code has been edited in a sensible way, running the program again should display the edited code. The definition of 'sensible' is left flexible to prevent this being impossible - as the source code can be edited, a user can obviously edit the program in such a way that it no longer displays it's source code.

The standard quine rule applies: no reading the source file directly.


Additional Notes and things to consider:

  • How robust is your program? What percentage of your program can be edited (sensibly) before it stops displaying it's own source or saving the edits you made.
  • Both overwriting and saving with a different filename are valid ways for the program to save it's new code
  • If it is a compiled language, the program does not have to invoke the compiler or do the compiling itself after saving.
  • This is a code challenge not code golf. Robustness, interface and 'coolness' of the solution are favoured over brevity.

  • Extra, uh, points(?!) if your program can identify errors in the quine before saving.


Is this a feasible challenge? Does it need clarification?

\$\endgroup\$
  • 1
    \$\begingroup\$ If the only winning-criteria is "Percentage of the characters which can be changed without breaking it" then the answerer can arbitrarily pad their score with an irrelevant string if their language has very versatile quining capabilities. The other things "favored" only really count if it's a popularity-contest and challenges with that tag are discouraged. \$\endgroup\$ – Kamil Drakari Sep 7 '17 at 21:07
  • \$\begingroup\$ Do you have any suggestions on how to score it? I can't think of any cross-language methods. \$\endgroup\$ – sdfgeoff Sep 7 '17 at 21:21
  • \$\begingroup\$ Currently you are scoring it as (characters that can change / total), You could square or cube the total to incentivise golfing, that way padding can only hurt you. However you want to watch out for very short programs that make little effort to complete the task but by virtue of their shortness are highly scoring. \$\endgroup\$ – Wheat Wizard Sep 17 '17 at 0:35
0
\$\begingroup\$

Prime Number Locator

Given a prime number p > 1, determine at what index p appears in A000040.

  • You may 0 or 1 index, meaning 2 can return 0 or 1.
  • If you are given a non-prime number you must return -1.
    • If you are 1-indexing you may return 0 instead, or still return -1.
  • Your time complexity must be less than O(n): Please explain your calculations in the answer.

First 10 return values (0-indexed):

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
[0, 1, 2, 3,  4,  5,  6,  7,  8,  9]

This is : Reduce your byte-count to win.

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – H.PWiz Sep 8 '17 at 17:41
  • \$\begingroup\$ @H.PWiz, I'd call that a dupe; the count is the index. \$\endgroup\$ – Shaggy Sep 9 '17 at 11:48
  • \$\begingroup\$ @Shaggy This one is restricted-complexity though \$\endgroup\$ – H.PWiz Sep 9 '17 at 12:00
  • \$\begingroup\$ o(n) is impossible: this isn't a problem which can be solved without reading all of the input. If that were relaxed to O(n) I think this would fit the "Too broad" close criterion because a properly explained answer would be a (very good) doctoral thesis. The current state-of-the-art algorithms are O(2^(2n/3) + epsilon), so a polynomial algorithm would already be impressive, and a linear one would be astounding. \$\endgroup\$ – Peter Taylor Sep 11 '17 at 8:59
0
\$\begingroup\$

Do the line segments cross?

Description: Today, we're going to do some geometry: We have two line segments and want to find out where they cross! A point is a pair of two integers being the x and y coordiantes of said point. If your calculations result in non-integers, you continue with the integer closest to your result.

I/O: You are given the two segments in form of 8 integers representing the 4 end points. You may take them in the order that fits you best, but you have to state the ordering. The output consisting of the point where the lines intersect, or null, an empty string or something similar, but no undefined behavior. You may use STDOUT, a file etc. to write your output.

This is - the shortest answer in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Can I take 4 tuples (x,y) instead? \$\endgroup\$ – H.PWiz Sep 8 '17 at 17:46
  • \$\begingroup\$ Of course. Are you golfing in Haskell? \$\endgroup\$ – racer290 Sep 8 '17 at 18:03
  • \$\begingroup\$ I'm not golfing now. Many languages have tuples. \$\endgroup\$ – H.PWiz Sep 8 '17 at 18:05
  • \$\begingroup\$ This is just a subset of this challenge. \$\endgroup\$ – AdmBorkBork Sep 8 '17 at 19:48
  • \$\begingroup\$ Only up to a certain degree. The challenge you mentioned is ok with a truthy/falsey value. That makes a difference in chosing your "algorithm". \$\endgroup\$ – racer290 Sep 9 '17 at 5:17
0
\$\begingroup\$

...?

Fork for n times

-bash: fork: HE COMES

TL;DR: fork up to n times, than hang forever

Relevant chat discussion

Your challenge is to make a program / function that calls itself twice or uses some other method of creating copies of itself that create copies of itself, etc.

However, to avoid crashing the system, your program limits itself before it forks to death. Given an input n, your program should stop forking when it has n total copies of itself (including itself), and keep running forever with n total copies of itself.


Meta

  • Under-specified?
  • Is the min of 500 good?
  • Tags?
  • Better title?
\$\endgroup\$
  • 1
    \$\begingroup\$ It's not exactly a dupe of this one, but that one is the same spirit, and it's closed and locked, so I wouldn't expect this to be well received. Also see this and this \$\endgroup\$ – DJMcMayhem Aug 22 '17 at 21:41
  • \$\begingroup\$ @DJMcMayhem see edits \$\endgroup\$ – programmer5000 Aug 22 '17 at 22:05
0
\$\begingroup\$

Where do I live? *

Given a coordinate pair, supporting at least 2 decimal places (precision .01), determine the country containing that coordinate pair. The coordinate will be on land and will be at least ~0.5 degrees (~50 km Great Circle distance; thanks Peter Taylor!) from any border or coastline.

Input will be given as two decimal numbers in any reasonable format. Output should be the English name of the country according to this source; spaces, accents, non-alphanumeric characters, and capital letters are all optional. For countries like Iran, you can choose to output either "Iran" or "Islamic Republic of Iran". The same applies for all ...Republic... countries, like N/S Korea, Lao, Taiwan, etc. For Côte D'ivoire, you can choose to output either "Côte D'ivoire" or "Ivory Coast".

Exact built-ins are not allowed (ahem Mathematica). Online APIs are not allowed (ahem Google Maps).

Western and Southern coordinates can be given as a negative decimal or with W and S (you can also have N and E if wanted). Please specify your input format.

You will have to handle coordinates in Antarctica. Apparently it's a country now.

Test Cases

Input           -> Output

43.26N,  79.54W -> Canada
37.42N,  94.88W -> United States of America
25.96N, 103.51W -> Mexico
 9.39S,  59.39W -> Brazil
79.66S,  65.22E -> Antarctica
90.00S,  00.00E -> Antarctica # It's such a shame that 90N ?E/W is in the middle of the ocean
74.25N,  40.00W -> Greenland
63.08N,  15.34E -> Sweden
66.19N,  98.93E -> Russia
30.72N, 103.39E -> China
 2.89S, 119.55E -> Indonesia
26.96S, 132.91E -> Australia

* not a real tag but I propose to add it

\$\endgroup\$
  • \$\begingroup\$ Does "at least 0.5 degrees from any border or coastline" mean "at least 55.6km from any border or coastline" (i.e. great circle distance)? \$\endgroup\$ – Peter Taylor Sep 11 '17 at 8:34
  • \$\begingroup\$ @PeterTaylor Yes, thanks for the calculation. I'll just say ~50 km, thanks. \$\endgroup\$ – HyperNeutrino Sep 11 '17 at 12:12
0
\$\begingroup\$

[tag:H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ]

Parse HTML with regex!

Alternate titles:

RegEx match open tags except XHTML self-contained tags

H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ - Parse HTML with regex

Background

Don't parse HTML with regex. It always fails and sometimes summons Cthulhu.

But, because PPCG is different, we will parse HTML with regex.

And not easy, beginner HTML. HTML with comments, attributes with no quotes, HTML in script tags not commented out and much more. Can you write a regex to parse that?

The challenge

Your challenge is to make a regex that matches valid HTML tags. Don't match comments, don't match invalid HTML, don't match HTML in comments, just match valid HTML tags. Each full regex match is one HTML tag.

Your input HTML will never contain commas. You will try to get the most points possible by successfully matching the HTML tags and not the text in as many inputs as possible. Whoever gets the most points wins. Please say at least 1 regex flavor that your regex works with.

You are not allowed to use regex features to execute language code. (Sorry, Perl)

The length of your regex is irrelevant, this is not code golf.

Test cases

Here are the test cases. You can also find them at https://hastebin.com/raw/mikaxakipe.txt.

1,1,<b>HTML!</b>,<b>,</b>
2,1,<i><b>HTML</b></i>,<i>,<b>,</b>,</i>
3,1,a < b implies b > a,
4,2,<img alt=text>Img,<img alt=text>
5,2,<a href = "http://example.com">Example Domain</a>,<a href = "http://example.com">,</a>
6,2,<hr><br/>,<hr>,<br/>
7,2,<div id ="hi" class="what">What</div>,<div id ="hi" class="what">,</div>
8,3,<a>fake</>,<a>
9,3,Self-closing <img src = "self-closing.jpeg" />?,<img src = "self-closing.jpeg" />
10,3,<self-closed/>O_O<unclosed>,<self-closed/>,<unclosed>
11,3,Do<yOU>like<LoTs>of<mIXeD><cAsE>?,<yOU>,<LoTs>,<mIXeD>,<cAsE>
12,3,Wh<a b='c'd="e">at?,<a b='c'd="e">
13,3,Hi<p data-hi=3>hihihi</p>,<p data-hi=3>,</p>
14,4,<a"oops">Oops,
15,5,<!-- <b><!--hi--><i>,<i>
16,5,<0>NOT VALID</0><h0>fine</h0>,<h0>,<h0>
17,5,<a a=b<>what</a>,<a a=b<>,</a>
18,6,<!-- <b><!--hi--><i>-->,<i>
19,7,<how><deep can><your nesting nesting><level></level></go>?<how>Deep</how><can><your>nesting <go x=? j><how><deep can><your nesting nesting><level></level></go>?<how>Deep</how><can><your>nesting <go x=? j><how><deep can><your nesting nesting><level></level></go>?<how>Deep</how><can><your>nesting <go x=? j></your></can></your></deep></how></your></can></your></deep></how></your></can></your></deep></how>,<how>,<deep can>,<your nesting nesting>,<level>,</level>,</go>,<how>,</how>,<can>,<your>,<go x=? j>,<how>,<deep can>,<your nesting nesting>,<level>,</level>,</go>,<how>,</how>,<can>,<your>,<go x=? j>,<how>,<deep can>,<your nesting nesting>,<level>,</level>,</go>,<how>,</how>,<can>,<your>,<go x=? j>,</your>,</can>,</your>,</deep>,</how>,</your>,</can>,</your>,</deep>,</how>,</your>,</can>,</your>,</deep>,</how>
20,7,<plaintext><b></plaintext>,<plaintext>,</plaintext>
21,7,What<img src="imgs/>lolz.png" alt = "<heh"/>,<img src="imgs/>lolz.png" alt = "<heh"/>
22,7,<b><a href = "#" title = "4 > 3">hi</a></b>,<b>,<a href = "#" title = "4 > 3">,</a>,</b>
23,10,<StYle><b title = "not in html"></style><B>HTML!</b><style></style>,<StYle>,</style>,<B>,</b>,<style></style>
24,10,<script>//<script>< /script></script><script></script><p>,<script>,</script>,<script>,</script>,<p>
25,10,<i></i this="will be removed by a browser">,<i>,</i this="will be removed by a browser">
26,10,<div id="hi" class=class="what" data-the="heck='is'this" get-good>Attributes are weird<div>,<div id="hi" class=class="what" data-the="heck='is'this">,<div>
27,10,<!--<b>Do you like comments??</b>--><p>,<p>
28,13,<textarea><script>/* *////*///*<!--</script><b>WHAT</b></textarea><i>Hi-->,<textarea>,</textarea>,<i>
29,15,<!--<b>Do you like comments??</b><script>--><script>//<!--hello</script><b>hi</b><!--What--><script>//<!-- <script> <!-- <script> --> </script><i>hello--><script></script>,<b>,</b>,<script>,</script>,<i>,<script>,</script>
30,15,<hi>hi</hi><0>hi</0><h0>hi</h0><h&>hi</h&><&>hi</&><??>hi</??><?php>hi</?php><php?>hi</php?><->hi</-><_-_>hi</_-_><h->hi</h-><_>hi</_><h-_>hi</h-_><?>hi</?><{>hi</{><h{>hi</h{></>hi<//><h~!@#$%^&*()>hi</h~!@#$%^&*()><h>hi</h><h~>hi</h~><h!>hi</h!><@>hi</@><h@>hi</h@><h!@#$%^&*()>hi</h!@#$%^&*()><@f>hi</@f><%>hi</%><;>hi</;><h>>hi</h>><h&>hi</h&><h~>hi</h~>,<hi>,</hi>,<h0>,</h0>,<H&>,</H&>,<PHP?>,</PHP?>,<h->,</h->,<H-_>,</H-_>,<H{>,</H{>,<H~!@#$%^&*()>,</H~!@#$%^&*()>,<H>,</H>,<H~>,</H~>,<H!>,</H!>,<h@>,</h@>,<h!@#$%^&*()>,</h!@#$%^&*()>,<H>,</H>,<H&>,</H&>,<h~>,</h~>
31,30,<hi>hi</hi><0 WHAT_is=HtMl>hi&<i attrubute="oops'></0><h0 attRiBu350Te="<b>oops</b><style>/*">hi</h0>*/<h&>hi</h&><&>hi</&><??>hi</??><?php>hi</?php><php?>hi</php?><->hi</-><_-_>hi</_-_><h->hi</h-><_>hi</_><h-_>hi</h-_><?>hi</?><{>hi</{><h{>hi</h{></>hi&<//><script>     &/*<h~!@#$%^&*()>*/</ script></StyLe>/*</ScrIPT>/*<b>oops</b>hi</h~!@#$%^&*()><h>hi</h><h~>hi</h~><h!>hi</h!><@>hi</@><h@>hi</h@><h!@#$%^&*()>hi</h!@#$%^&*()><@f>hi</@f><%>hi</%><;>hi</;><h>>hi</h>><h&>hi&</h&><h~>hi/*/</h~><b>oops</b>hi</h~!@#$%^&*()><h>hi</h><h~>hi</h~><h!>hi</h!><@>hi</@><h@>hi</h@><h!@#$%^&*()>hi</h!@#$%^&*()><@f>hi</@f><%>hi</%><;>hi</;><h>>hi</h>><h&>hi&</h&><h~>hi/<script></StyLe></ScrIPT><textarea><b>HE COMES</b></textarea><h!>hi</h!><@>hi</@><h@>hi</h@><h!@#$%^&*()>hi</h!@#$%^&*()><@f>hi</@f><%>hi</%><;>hi</;><h>>hi</h>><h&>hi&</h&><h~>hi</h~>,<hi>,</hi>,<i attrubute="oops'></0><h0 attRiBu350Te="<b>,<style>,</style>,<textarea>,</textarea>,<h!>,</h!>,<h@>,</h@>,<h!@#$%^&*()>,</h!@#$%^&*()>,<h&>,</h&>,<h~></h~>

Each line is a separate test case. They are in this format:

1,1,<b>HTML!</b>,<b>,</b>
| | |            |   |
| | |            +---+- The correct output: all HTML tags in the string separated by commas
| | +- The HTML for you to parse
| +- The number of points you get if you parse this HTML correctly
+- The test case number

Example

Let's say we have the regex /<.*?>/g (all flavors). For test case #1, it matches 2 times: <b>, and </b>. The correct output in the test case says that it should match <b> and </b>, so it is correct. Our regex gets 1 point.

Then for test case #2. Our regex matches <i>, <b>, </b>, and </i>, which is consistent with the test case so we get 1 point.

Now for test case #3. Our regex matches < b implies b >, when it should have not matched anything. We get 0 points for that.

Continuing for each test case gets us a score of 50 (out of 207, or 24.15%). Not great. Can you do better?

Try It Online

If your regex will work with the ECMAScipt / JS flavor than you can try it here and get automatic scoring!

Tie breaker

Here are the scoring systems. Whoever has the best score on the first wins. In the event of a tie, whoever out of the ties scores the best wins, etc.

  1. Most points
  2. Shortest length
  3. First posted

Answer format

[insert score here] / 207 points

[insert regex here]

Explanation (optional but encouraged)

Proof of score (matched output vs. test cases, link to TIO to try it, etc.)


Meta

\$\endgroup\$
  • \$\begingroup\$ Any tie breaking for regexes with the same score, e.g. length? \$\endgroup\$ – Laikoni Sep 11 '17 at 5:28
  • 1
    \$\begingroup\$ 1. This is a meta-regex question, and scoring it just on test cases means that there are already programs out there which will generate a regex that gets a perfect score. As it stands it's a pretty pointless contest. 2. I don't see a specification for an HTML tag, or even a link to one. Why, for example, is < b implies b > invalid? Without a spec it's even more a meta-regex question rather than an HTML question. 3. This isn't parsing HTML with regex. It's closer to lexing HTML with regex, and no-one said that that was impossible or would summon the Elder Ones. \$\endgroup\$ – Peter Taylor Sep 11 '17 at 7:50
  • \$\begingroup\$ @Laikoni status-completed \$\endgroup\$ – programmer5000 Sep 11 '17 at 21:10
0
\$\begingroup\$

Matrix Decomposition

Meta

  • Duplicate?
  • What rules should I add?
  • Are my explanations sufficient?
  • Any room for improvement?

It's possible to "factor" any invertible (a.k.a. non-singular) square matrix A into a combination of a permutation matrix1 (P), a unit3 lower triangular matrix2 (L), a diagonal matrix4 (D), and a unit upper triangular matrix2 (U).

That is, A = PLDU

For instance, the matrix [[4, 5], [2, 3]] can be expressed as the multiplication of the following matrices:

P = [[0, 1],
     [1, 0]]
L = [[1, 0],
     [2, 1]]
D = [[2, 0 ],
     [0, -1]]
U = [[1, 3/2],
     [0, 1  ]]

Task

Given an invertible square matrix A, output P, L, D, and U.

Test Cases

TBD

Rules

  • Any reasonable output format is acceptable, but P, L, D, and U must be separate outputs.

1. A permutation matrix is a permutation of the identity matrix.

2. An upper triangular matrix is a square matrix whose nonzero values occur only on or above the main diagonal, and a lower triangular matrix is a matrix whose nonzero values occur only on or below the main diagonal.

3. A unit triangular matrix is a triangular matrix whose main diagonal is all 1s.

4. A diagonal matrix is a matrix whose nonzero values occur only on the main diagonal.

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

Become a Word-Pontif

The french used to define the word pontif as one who builds bridges stemming from the conjunction of pons, facere which literally translates to a bridge, to create one. Your task will be, given a list of 1 or more lower-case words l (String Array), output the MAXIMUM length of a bridge that can be built from these words.


Bridge Rules

  • Bridges can be made by connecting two or more words together:
    • Words must be connected prefix-to-suffix or suffix-to-prefix.
      • To join two words into one:
        • The suffix of the first must match the prefix of the second (abc+cba=abcba).
        • The prefix of the first must match the suffix of the second (earl+toe=toearl).
    • If a word's prefix/suffix contains more than one common character:
      • You can only connect them with the maximal common substring.
      • In other words,abc and bcdefg can be connected using a[bc]defg.
  • The length of a bridge is simply the length of the conjoined words in characters.

Building Material Rules

  • The list will contain at fewest 1 word.
  • The list may hold 0 links between words, in this case the maximal size is the longest word in the list.
  • The list will not contain the empty string and will only use the lowercase alphabet (a-z).
  • The list MAY NOT contain duplicates.

Examples

Example 1:

[abcdefgh,holographic,graphical,quine,loitering]

abcdefholo[graphic]al = 19

19

Example 2:

[noon,moon,loon,noon,groom]

groo[m]oon

8

Example 3:

[spoon,whatifgodwereoneofus,oneofusisatraitor,aaaaaaaaaaaaaa,aaaaaaaaaa]

whatifgodwere[oneofus]isatraitor (because the two aaaaa's overlap too much).

30

Example 4:

[abc,def,ghi,jkl,mnop,qrst,uvwxyz]

uvwxyz (No matches)

6

Example 5:

[xox,xxox,lol,lolol,lololol,xoxx]

xo[xx]o[x]ox    < 8  (Maximal of the xox path)
[lol]o[l]ololol < 10 (Maximal of the lol path)

10

Example 6 (Base):

[hi]

hi

2

Example 7:

# Note, when a link has been used it cannot be used twice.
# In other words, the brackets used cannot overlap in these examples.
[aa,aaa,aaaa] 

aa[aa][a]a (Chose to use aaaa,aaa,aa)

7

General Rules

\$\endgroup\$
  • \$\begingroup\$ 1. This is extremely close to codegolf.stackexchange.com/q/132561/194 . 2. Examples 5 and 7 look wrong. \$\endgroup\$ – Peter Taylor Sep 12 '17 at 8:52
  • \$\begingroup\$ In example 1, isn't it abcdefgholographicaloitering = 28? \$\endgroup\$ – KSmarts Sep 18 '17 at 14:22
0
\$\begingroup\$

Validating Words in Word Grids

A follow on from Generating Word Grids

Given a grid of letters and a set of co-ordinates, validate that the co-ordinates follow only cardinal direction changes, at least one of the co-ordinates touch an empty space in the centre of the grid, the resulting word is valid given the dictionary (taking into consideration any blank tiles) and return either the grid, with the letters at the co-ordinate removed along with the score of the word, or, if one of the conditions fails, the original grid and a score of -1.

Details

Please use the dictionary provided which is a /usr/bin/dict clone with all words converted to lowercase, non-alphabetic characters removed, and then de-duplicated.

0,0 will be the uppermost, leftmost character on the grid, working right and down.

Scoring

Letters are worth their values as per Scrabble:

0 points: blank tiles
1 point: E, A, I, O, N, R, T, L, S, U
2 points: D, G
3 points: B, C, M, P
4 points: F, H, V, W, Y
5 points: K
8 points: J, X
10 points: Q, Z

Bonus tiles (indicated by a lowercase letter, or ! for a blank tile) provide a *2 multiplier and stack (eg. if my co-ordinates spell gOLf I would earn (((2+1+1+4)*2)*2), 32 points).

Examples:

Input:

6,4 6,5 5,5 4,5 3,5 3,6 2,6 1,6
UWDESTKP?
ItDBaDEdI
TERMDYTSR
ROANJLEFT
EkCI OOsT
IPAJPGMNY
MZLORITVI
GwEGgPUeI
MNROYOEER

Output:

9
UWDESTKP?
ItDBaD dI
TERMDY SR
ROANJ  FT
EkCI  OsT
IPAJP MNY
MZLO  TVI
GwEGgPUeI
MNROYOEER

(spells RIGOLETE, (1+1+2+1+1+1+1))

Input:

0,3 0,4 0,5 0,6
UWDESTKP?
ItDBaD dI
TERMDY SR
ROANJ  FT
EkCI  OsT
IP  P MNY
MZL   TVI
GwE gPUeI
MNROYOEER

Output:

-1
UWDESTKP?
ItDBaD dI
TERMDY SR
ROANJ  FT
EkCI  OsT
IP  P MNY
MZL   TVI
GwE gPUeI
MNROYOEER

(spells DEST which doesn't appear in the dictionary)

Input:

5,6 4,6 4,7 4,8
UWDESTKP?
ItDBaD dI
TERMDY SR
ROANJ  FT
EkCI  OsT
IP  P MNY
MZL   TVI
GwE gPUeI
MNROYOEER

Output:

12
UWDESTKP?
ItDBaD dI
TERMDY SR
ROANJ  FT
EkCI     
IP  P  NY
MZL   TVI
GwE gPUeI
MNROYOEER

(spells MOsT, (3+1+1+1)*2)

Rules

This is so the shortest code in bytes wins.

  • The order is not important, it can be score then grid, or vice versa.
  • Any reasonable format can be used for I/O assuming it is consistent.
  • All standard loopholes are forbidden.

\$\endgroup\$
  • \$\begingroup\$ This looks pretty good to me. \$\endgroup\$ – Rɪᴋᴇʀ Sep 15 '17 at 18:20
  • \$\begingroup\$ Thanks @Pavel, I'll bear that in mind, i'm not sure how much interest there is based off of part 1, but I might still post this in the next week or so :) \$\endgroup\$ – Dom Hastings Sep 16 '17 at 9:21
0
\$\begingroup\$

Word Grid Pathfinding

A follow up to Generating Word Grids and Validating Words in Word Grids.


Meta

My original idea for this was to have entries compete, but I'd like to have different winning conditions. Given grid x, pit all scripts against each other for the following win criteria:

  • Highest Score
  • Shortest Path
  • Fewest remaining tiles
  • Longest Words

but I think perhaps just making it code golf and offering a bounty to each of the criteria above after some time. I'd like some feedback on this. I like @LegionMammal978's idea, but feel like perhaps that could be a separate challenge (again, only if these are interesting to anyone!)


Given a grid of letters, complete a path of words that reaches from the centre of the board, to the edges. You must return lists of your moves as co-ordinates and your score will be tallied. As soon as there is a clear path from the centre to the edge, the game is over, and no further words will be scored.

Details

Grids will always have an equal, odd, number of rows and columns, such that no direction contains fewer tiles.

Restrictions

In the event that the grid is unsolvable (or becomes unasolvable because of your chosen path, you may return something falsy instead of a list of co-ordinates.

Your script must be able to handle grids of varying sizes and solve them in a reasonable time, such that a service like TIO can be used, without causing problems in most cases, for extremely large inputs (> 500). You are free to take input in any reasonable format, but please include a link to your script with a wrapper such that it can take input in via STDIN/script arguments via an online service.

#TODO: copy details of the adjacency rules from above.

For example, in the grid provided below, the J, I, P or O letters (north, east, south and west of the blank square) must be included, once this word has been removed, you have more available words.

There are bonus letters that provide a double point score, denoted by a lowercase letter or ! (instead of ? for a blank tile). Blank tiles are used exactly as they are in Scrabble and can count as any letter, the validating program will search for words replacing the ? (or !) with a wildcard. Letters are scored as per Scrabble:

0 points: blank tiles
1 point: E, A, I, O, N, R, T, L, S, U
2 points: D, G
3 points: B, C, M, P
4 points: F, H, V, W, Y
5 points: K
8 points: J, X
10 points: Q, Z

Your score will be calculated by the validator.

Examples

Input:

UWDESTKP?
ItDBaDEdI
TERMDYTSR
ROANJLEFT
EkCI OOsT
IPAJPGMNY
MZLORITVI
GwEGgPUeI
MNROYOEER

Output:

6,4 6,5 5,5 4,5 3,5 3,6 2,6 1,6
5,6 4,6 4,7 4,8

Total moves: 2
Points: 21

#TODO: more examples.

\$\endgroup\$
0
\$\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\$
  • \$\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\$ – dkudriavtsev 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
0
\$\begingroup\$

Shift-left golfer

Sometimes when doing code-golf, a person needs to understand which format is shorter:

  • 2147483648
  • 0x80000000
  • 1<<31

The task:

You will receive a number in one of the three formats above: decimal, hexadecimal, or shift-left operation. If there is no advantage in converting it to another format, just leave the number the way it is; otherwise I want the shortest format. Of course there are numbers you can't convert to shift-left format!

Notation:

  • Hexadecimal0x#######.... where there are no leading zeros after the x. When accounting for evaluating the golfiness, the 0x part is also taken into consideration. For example 0x80000000 has a length of 10.

  • Decimal#######.... where there are no leading zeros.

  • Shift-left#...<<#.... no leading zeros both sides of <<. The << operator is also considered for length, e.g 1<<31 has a length of 5. You must also handle multiple digits before the << signal.

# represents a digit and ... represent possible repetition of digits

I don't care if you handle leading zeros at the input or not; but if you handle them, you must do the comparison operations without them and output also without them — You're a golfer, come on! You will understand!

There will be no accepted answer.

, so I want to know shortest answer by language.

UPDATE 1:

In spite of @dzaima 's comment, now it also needs to handle multiple digits before << signal.

\$\endgroup\$
  • 1
    \$\begingroup\$ How about just take an integer as input and return the shortest form as output? \$\endgroup\$ – HyperNeutrino Sep 15 '17 at 19:20
  • \$\begingroup\$ 1<<31 has a length of 4 not 5? \$\endgroup\$ – Rɪᴋᴇʀ Sep 15 '17 at 22:38
  • \$\begingroup\$ @Riker: Sorry, my mistake. Now fixed. \$\endgroup\$ – sergiol Sep 15 '17 at 22:59
  • \$\begingroup\$ @dzaima: Updated. Yes, it will need to handle multiple digits before << \$\endgroup\$ – sergiol Sep 16 '17 at 11:07
  • \$\begingroup\$ If you allow non-ones in front of the byte shift as input, but not as output, an input like 99<<99 would result in the output having more bytes than the input. \$\endgroup\$ – Jonathan Frech Sep 18 '17 at 5:23
  • \$\begingroup\$ What about something like 0x45<<0x378? i.e., why not hex numbers in left-shifts? \$\endgroup\$ – wastl Jul 7 '18 at 20:38
0
\$\begingroup\$

Translate Tetris moves to GoL!


Unless you've been living under a rock, you're probably aware of the fact that the highest voted unanswered, incredibly hard challenge to build a working game of Tetris in Conway's Game of Life just recently got answered. (Go check it out if you haven't already.)

Unfortunately, since this game is written in Conway's Game of Life, giving input to the code is a bit tricky. (Of course, if they can simulate Tetris in GoL, you can play it with tricky moves. :P) To quote the main answer:

Each move only requires editing a single bit of RAM, and this input register is automatically cleared after the input event has been read.

Each Tetris move corresponds to a single number by the following table:

value     motion

1         counterclockwise rotation
2         left
4         down (soft drop)
8         right
16        clockwise rotation

Now, of course, if there was only a way to automate this...

Challenge

Write a program/function that takes a series of keypresses as input and outputs each keypress' respective number according to the table above.

The keypresses should map as the following:

value            motion

<                counterclockwise rotation
<left arrow>     left
<down arrow>     down (soft drop)
<right arrow>    right
>                clockwise rotation

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that perform this task are allowed but including a solution that doesn't rely on a built-in is encouraged. (Pshh, how likely is that?)
  • Explanations, even for "practical" languages, are encouraged.

Test cases

// incoming

Sandbox

  • Should I switch from keypresses to strings of ( < v > )?
  • I'm really lacking on tags...
  • Bump!
\$\endgroup\$
  • 2
    \$\begingroup\$ Not all languages can support keypresses, so using a string would be better. \$\endgroup\$ – fireflame241 Sep 23 '17 at 18:20
  • \$\begingroup\$ Also, if you go for keypresses: What happens if I hold a key for 10s? What happens if I hold a key and simultaneously press another one? \$\endgroup\$ – ბიმო Sep 25 '17 at 11:04
0
\$\begingroup\$

Two-Symbol n-state Universal Turing Machine

A program is defined as a set of transition rules from one state to another based on the current state and symbol, optionally moving the tape head left or right.

The goal is to produce a program that satisfies all of the following criteria:

  • It is a two-symbol Turing Machine program.
  • It emulates a two-symbol Turing Machine program that is represented on the tape.
  • where all tape that is not data is initialised to one symbol (designated 0 - the other is 1).

There are two scoring criteria:

  1. The number of states. Smaller is better.
  2. The compressibility of the program format (see below).

There is an individual scoring for each criterion and a combined position. The combined position is the sum of the ordinal positions in the leaderboard for each criterion (e.g. if your solution is 1st for number of states but 4th for compressibility it has a combined position of 5th). In the likely event of a tie, the compressibility of the program format is the tie-breaker.

Compressibility of the Program Format

The compressibility of the program format is defined as the number of (additional) states required to write the program onto a blank (0) tape, move the head to the start position of the program and start running the emulator on the program (change state to a correct emulator state). Sandbox note: Hand-compressed test-cases? Average-case Big O?

\$\endgroup\$
  • \$\begingroup\$ Todo: Work in a reference to this article and how a good solution to this challenge will reduce the upper bound for the maximum computable value of the Busy Beaver function. \$\endgroup\$ – wizzwizz4 Sep 22 '17 at 20:49
  • \$\begingroup\$ Is there a way to tell the Kolmogorov complexity when compressed through a certain method? It seems like the compressibility of the input format is poorly defined and will vary between inputs. \$\endgroup\$ – wizzwizz4 Sep 22 '17 at 20:54
  • \$\begingroup\$ I'm not quite seeing the busy beaver connection. Clearly it's not about emulating a single program, because in general the program itself would have fewer states than the program which puts it onto the tape and then runs the emulator; so it must be about some kind of loop over all programs, but then you run into undecidability of the termination of the emulator programs, meaning that the emulator certainly doesn't terminate. \$\endgroup\$ – Peter Taylor Sep 23 '17 at 20:25
0
\$\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\$
  • \$\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
0
\$\begingroup\$

It’s raining numbers! Better to get a good umbrella!

Your task is to take in one integer input and print a “raining” alternating pattern with that number, and an umbrella of appropriate size to protect yourself from such a rain!

Examples

1 =>

  1
 _|_
/   \
-----
  |
  C


2 =>

  2  
      2
 ___|___
/       \
---------
    |
    |
    C


3 =>

  3       3
      3  
  3       3
 _____|_____
/           \
-------------
      |
      |
      | 
      C


4 =>

  4       4
      4       4
  4       4
      4       4       
 _______|_______
/               \
-----------------
        |
        |
        |
        |
        C


10 =>

  1       1       1       1       1
  0       0       0       0       0
      1       1       1       1       1
      0       0       0       0       0
  1       1       1       1       1
  0       0       0       0       0
      1       1       1       1       1
      0       0       0       0       0
  1       1       1       1       1
  0       0       0       0       0
      1       1       1       1       1
      0       0       0       0       0
  1       1       1       1       1
  0       0       0       0       0
      1       1       1       1       1
      0       0       0       0       0
  1       1       1       1       1
  0       0       0       0       0
      1       1       1       1       1
      0       0       0       0       0    
 ___________________|___________________
/                                       \
-----------------------------------------
                    |
                    |
                    |
                    |
                    |
                    |
                    |
                    |
                    |
                    |
                    C

Rules

  • The output should use only the ascii characters _ | - / \ C, space, and the digits (no tabs are allowed).
  • Numbers should have an alternating pattern, two digits on the same line are separated by 7 spaces.
  • Number with more than one digit must be written vertically.
  • The size of the first line of the top of the umbrella should be equal to 4n-1, for input n, centered below the “rain”; the size of the second line should be equal to 4n+1.
  • The shank of the umbrella under the top is centered and should be of height n (the | characters), and terminated by a C handle.
  • Lines can have trailing spaces.

This is a task, so the shortest solution is any language wins.

\$\endgroup\$
  • \$\begingroup\$ shortest solution in any \$\endgroup\$ – Adám Sep 27 '17 at 7:36
  • \$\begingroup\$ I think that you should explicitly state the input for each example output. \$\endgroup\$ – H.PWiz Sep 27 '17 at 9:21
  • \$\begingroup\$ Allowed whitespace should be mentioned in the first rule. Regular spaces seem obvious, but using tab characters in place of 4 spaces could be used and it's a good idea to explicitly allow or forbid it. Also, that rule should start with "The output should..." to clarify that this is not restricted-source \$\endgroup\$ – Kamil Drakari Sep 27 '17 at 14:46
0
\$\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
    \$\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
0
\$\begingroup\$

Sort a nested object by nested value

Your goal is to sort a nested object by a nested value. What does that mean? For example:

#1: Input

{
    foo: {
        category: "A",
        hello: "world",
        color: "blue"
    },
    bar: {
        category: "B",
        cu: "cumber",
        color: "blue"
    },
    baz: {
        category: "A",
        let: "tuce",
        color: "green",
    }
}

#1a: Output sorted by category

{
    A: {
        foo: {
            hello: "world",
            color: "blue",
        },
        baz: {
            let: "tuce",
            color: "green"
        }
    },
    B: {
        bar: {
            cu: "cumber",
            color: "blue"
        }
    }
}

#1b: Output sorted by color

{
    blue: {
        foo: {
            hello: "world",
            category: "A"
        },
        bar: {
            cu: "cumber",
            category: "B"
        }
    },
    green: {
        baz: {
            let: "tuce",
            category: "A"
        }
    }
}

Note that the sorting key is always deleted from the objects (when sorting by color none of the items contain color).

Your task

Given an object, and a sorting key (a string), output the sorted object as shown.

Rules

  • You can always assume that the value of the sorting key is a string (as it also needs to be a key in the output)
  • You can always assume that the given sorting key exists in all values
  • Sorting will only occur on the first-level objects, but the sorting key can be nested (see test case #2)
  • The object may be a JSON object, a python dict, a JS object, etc. but must always have string only keys.
  • You may accept the object as a JSON string and/or return a JSON string.

Test Cases

#2: Input

Sort by: rating.healthiness

{
    icecream: {
        sweet: true,
        rating: {
            tastiness: "8",
            healthiness: "4"
        }
    },
    pizza: {
        sweet: false,
        rating: {
            tastiness: "9",
            healthiness: "3"
        }
    },
    chocolatecake: {
        sweet: true,
        rating: {
            tastiness: "8",
            healthiness: "3"
        }
    }
}

#2: Output (sorted by rating.healthiness)

{
    "3": {
        pizza: {
            sweet: false,
            rating: {
                tastiness: "9"
            }
        },
        chocolatecake: {
            sweet: true,
            rating: {
                tastiness: "8"
            }
        }

    },
    "4": {
        icecream: {
            sweet: true,
            rating: {
                tastiness: "8"
            }
        }
    },
} 

Sandbox Questions

  1. I really need to make the question clearer. Any thoughts? How can I better describe the task?
  2. Is this a duplicate?
  3. I'm guessing I need a better title. Any ideas?
  4. Should I make the input a JSON object or just a general object?
  5. Are multi-level nested objects even possible? Would it be too easy without them?
  6. Should I also allow booleans & numbers as the value for the sorting key (and then in a key form it would be stringified)?
\$\endgroup\$
0
\$\begingroup\$

Output the Yggdrasil graph

In Norse mythology, Yggdrasil, or the world tree, is a giant tree that spans the entire universe and connects all nine worlds of the Norse mythology together. Here, we shall take a rather liberal reinterpretation of the term "world tree" - it's the tree that contains all other trees as subgraphs. Not only that, but each graph is present everywhere in Yggdrasil. Clearly, the only way to achieve that is if every node in the graph has infinitely many neighbors.

Yggdrasil is the unique (up to isomorphism) non-empty graph with the two properties that each vertex has ℵ₀ neighbors and that there is a unique simple path between any two vertices. In other words, Yggdrasil is the Cayley graph of the free group with countably infinitely many generators. Your goal is to output this graph.

Nodes can be given any printable label of your choice, as long as they are non-empty and unique within the graph. Edges shall be denoted as pairs of vertices in either order. It must be clear from the output which are the two nodes in a graph (a-b-c is not an acceptable representation of an edge from a-b to c, but ["a-b", "c"] is fine). In the output, each edge shall be output on a single line, and different edges shall go on different lines.

The output should be just the list of edges in the graph, one edge per line. Each edge in the graph must be output exactly once, and in a finite amount of time (barring memory limitations). Edges not in the graph must not be output. For example:

  • Listing the edges in breath-first order is not sufficient, as any edge disjoint from the root would not get output.
  • Listing the edges in depth-first order is not sufficient, as no more than two edges of any node would ever get output.
  • It is sufficient (but not necessarily optimal) to generate the output by repeating (for each node in a copy of the list of known nodes, take the first unknown child, output the edge to it and add it to the list of known nodes).

The sufficient example above will output, if nodes are labeled 0, 0 1, 0 2, 0 1 1, ... :

0 => 0 1
0 => 0 2
0 1 => 0 1 1
0 => 0 3
0 1 => 0 1 2
0 2 => 0 2 1
0 1 1 => 0 1 1 1
...
\$\endgroup\$
  • \$\begingroup\$ So basically we have a countably infinite set of vertices V, a countably infinite index set I, and an injection (V x I) -> V. Since any bijection is an injection, we can use minor variants of e.g. codegolf.stackexchange.com/q/8892/194 , codegolf.stackexchange.com/q/78606/194 , codegolf.stackexchange.com/q/48705/194 with a loop for(n=0;;n++) wrapped round to create a valid answer. So although quite well disguised this is actually a dupe. \$\endgroup\$ – Peter Taylor Oct 3 '17 at 8:34
  • \$\begingroup\$ @PeterTaylor not sure how that would work. Are you trying to output the complete infinite graph rather than the infinite order regular tree? \$\endgroup\$ – John Dvorak Oct 3 '17 at 9:00
  • \$\begingroup\$ Use the reverse direction of the bijection: N -> (N x N). Then for(n=0;;n++)print(unpair(n)[0],"=>",n). Every node has an infinite number of successors, but each node has only one predecessor, so it's a tree. For the previous questions which use a bijection N -> (Z x Z) it's ever so slightly more subtle: to enumerate the entire tree we need to add in a bijection N -> Z and write for(n=0;;n++)print(unpair(n)[0],"=>",z(n)), but there are some very simple bijections N -> Z. \$\endgroup\$ – Peter Taylor Oct 3 '17 at 9:28
0
\$\begingroup\$

Is my Sukkah Kosher?

Do not rely on this text for questions of Jewish law!

You will be given a floor plan of a sukkah as follows:

  • A rectangular 2D text (in any reasonable format).
  • The first and last rows and columns will consist of printable ASCII (32-126).
  • All interior characters will be spaces.

Determine if the sukkah is acceptible according to these simplified rules, using the scale of one character width/height representing the tefach unit.

  • The inner area, as encompassed by the completion of the two longest solid walls into a square, must be at least 6 units by 6 units.

  • If the two longest solid walls are across from each other, then the shorter one must be at least 6 units long, and the length with with they are diametrically across from each other must also be 6 units long.

  • There must be an additional wall which is at least one unit long.

  • The walls may be made of any material, i.e. any character except space.

  • Walls with single unit gaps are still considered solid.

You may answer with any two distinct values, but please specify if different from true/1 and false/0. Explanations are appreciated.

Acceptable

oOOOo.ooo...o--o   
#              @   
#              )   
#              (   
#                  
|                  
#                  
+++++++*******     

oOOOo.ooo...o--o   


                 @   
                 @   
                 @   

   +++++****         

o O o o o . o        


                 @

                 @   
                 @   

   +++++****        

Not acceptable

oOOOo.ooo...o--o   
#              @   
#              )   
               (   

|                  
#                  
++++      ****     

       oOOOo.ooo..


                 @   
                 @   
                 @   

+++++****         

o O o o o . o        


                 @

                 @   
                 @   
                 8  
                 8

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

A Conc-urn-ing Problem

You have a mysterious urn, which contains 0 <= n <= 10 sets of k balls. Each set of balls shares a numeric label, from zero to n-1. You perform a repeated experiment, wherein you remove a ball from the urn, and note its number. If the number of balls in the urn with the same label as the ball you removed has the highest or tied for highest frequency still in the urn, you put the ball back in.

Taking the recorded results of each of the trials yields an infinite sequence. For example, you might have for n=2, k=2 pulled: 1001000000...

Given n and k write a program or function that returns a regular expression which will match any valid real number generated by this process, and which fails to match any other real number.

Sandbox

This is missing quite a bit (haven't written a program yet), but I'm not sure if it is too tedious the way that it currently is. It's somewhat boring if restricted to n=2 but rather quickly becomes tedious after that. Since most of the result would be symmetric, would it make sense to only require the "first" result? This also seems like it removes too much of the interest in the problem.

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

Search Stack Overflow for Duplicates

The Stack Overflow search algorithm has been under fire recently. Several problems with the search algorithm being flawed exist, but one of the most important issues raised is with duplicates:

[...] The search engine is used while authoring a question to find potential duplicates. At that point there is no way for you to take advantage of its features through custom search operators, and it absolutely, positively must be as good as an external search engine in this scenario. Unfortunately, it isn't. – IInspectable (source)

A flawed duplicate search algorithm causes a lot more work for the comparatively few reviewers and duplicate closers than there should be, by not informing the question askers that the question that they are attempting to post is a duplicate. It is also bad for the question askers, preventing them from finding the answer to their question until somebody reviews the question.

This is where you come in. Given the title, body and tags of a question, output a list of 25 relevant questions in a reasonable format (e.g. question ids). Your program should run within 500ms on the Stack Exchange servers for each question. (Sandbox note: How fast are the Stack Exchange servers? What conversion factor should I use to test on my hardware?) You have access to all T-SQL database tables available from the Stack Exchange Data Explorer, but the current question that needs to be checked for duplicates will be absent from all tables (so it isn't found as a duplicate of itself). To test the algorithm, it would be tested on a random selection of or all of the existing duplicates on Stack Overflow - the algorithm with the lowest average position of the duplicate master(s) in the list would win, where "not in the list" is counted as 50. The set of existing duplicates tested would be the same for all algorithms to test - rationale includes scoring of questions with multiple duplicate masters. The search algorithm should be deterministic. It is allowed to prepare a cache table beforehand - none of the duplicates to test will be passed to this part of the algorithm. This cache table should be able to be updated with new questions without being completely rebuilt. (Sandbox note: How to score this?)

(Sandbox note: The final paragraph should be spread out and better laid out and reworded, but I think the wall of text contains enough information.)

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

Constructively golf true primes!


Introduction

A recurring pattern that I see in challenge involving primes is the (over-) use of prime-checking built-ins and of factorization built-ins. However, I kinda don't trust especially the latter, which is why today, we're gonna build primes and include a certificate that the result is actually a prime.

Input

A positive integer n denoting the length of the resultung prime in a basis of your choice.

Output

A list of primes in the base you picked above, one of these primes is of length n and one of these primes is smaller than 20.

What to do?

Your challenge is to generate a prime of length n of which the primality can be reduced to the primality of one of the following primes: [2,3,5,7,11,13,17,19]. This can be achieved using Pocklington's criterion. Now the idea is to chain up from any of these primes using said criterion to a prime of appropriate size, while also outputting the intermediate steps so primality can be checked easily.

For your convenience, I shall reproduce the relevant theorem here:

Let N>1 be an integer and suppose there exist a,q such that

  • q is prime
  • q divides N-1
  • q>sqrt(N)-1
  • a^(N-1) mod N == 1
  • gcd(a^((N-1)/q)-1,N)=1

Then N is prime.

And as you might see, your initial set of primes (as candidates for q) is limited to the above short list of primes smaller than 20.

Who wins?

This is so the shortest solution in bytes wins!
However this is also so all solutions must run in (expected) polynomial time in n. Standard IO and Loophole rules apply.

Got any help?

If you need algorithmic help, I suggest you consult the Handbook of Applied Cryptography, chapter 4 (PDF), algorithm 4.62 (on page 153 or 22 in the PDF) or you independently look for Maurer's prime generation algorithm (originally published here).

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

I got them Mad Matrix Moves


Given a list of edges representing a simple directed graph and (optionally) the number of vertices n>1, output the adjacency matrix of that graph.

The vertices will always be numbered consecutively starting at 0 (or 1 -- your choice).

The adjacency matrix is defined as the n by n square matrix M such that M[i][j] is 1 if there is an edge from vertex i to vertex j and 0 otherwise.

Example

For this example and the test cases, we will have the vertices numbered starting at 1.

Let's use the sample input [(1,2),(1,3),(3,2)]. Since there are vertices numbered 1-3, n=3 and our output is a 3 x 3 matrix.

The output should be

[[0, 1, 1],    <= (1,1) doesn't exist in the input list, (1,2) does, (1,3) does.
 [0, 0, 0],    <= (2,1) doesn't exist, same with (2,2) and (2,3)
 [0, 1, 0]]    <= (3,1) doesn't exist, (3,2) does, and (3,3) doesn't

(concisely represented as [[0,1,1],[0,0,0],[0,1,0]] in test cases).

Notes

  • Every vertex is the start and/or end of at least one edge.
  • You may replace 1 and 0 in the output with any two consistent distinct values of your choosing.
  • The input graph is simple, meaning that it has no loops nor multiple edges (e.g. no edge [1,1] or graph [[1,2],[1,2]])
  • The graph is directed, meaning that each edge has a start and an edge (e.g. the edge [1,2] is distinct from [2,1])
  • Every vertex is an endpoint of at least one edge
  • This is , so shortest code in byes in each language wins.

Test Cases

One test case per line. Each test case is in the format edges, n => output.

[(1,2)], 2 => [[0,1],[0,0]]
[(2,1)], 2 => [[0,0],[1,0]]
[(1,2),(2,1)], 2 => [[0,1],[1,0]]
[(1,2),(1,3),(3,2)], 3 => [[0,1,1],[0,0,0],[0,1,0]]
[(1,2),(2,3),(3,4),(4,5)], 5 => [[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0]]
[(1,2),(3,4),(4,3),(2,1),(2,4),(4,2)], 4 => [[0,1,0,0],[1,0,0,1],[0,0,0,1],[0,1,1,0]]
[(1,2),(2,3),(3,4),(4,5),(2,1),(3,2),(4,3),(5,4)], 5 => [[0,1,0,0,0],[1,0,1,0,0],[0,1,0,1,0],[0,0,1,0,1],[0,0,0,1,0]]
[(1,2),(3,1),(2,3),(1,1),(2,1)], 3 => [[1,1,0],[1,0,1],[1,0,0]]
[(1,2),(3,2),(1,3),(5,4),(5,6),(5,1),(2,3),(1,5),(5,2),(3,6),(4,5),(5,3),(2,1),(3,5),(4,6),(6,3),(6,5),(4,2),(3,4)], 6 => [[0,1,1,0,1,0],[1,0,1,0,0,0],[0,1,0,1,1,1],[0,1,0,0,1,1],[1,1,1,1,0,1],[0,0,1,0,1,0]]
\$\endgroup\$

You must log in to answer this question.

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