557
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

4111 Answers 4111

1
122 123
124
125 126
138
0
\$\begingroup\$

I X the source code, you Y the output!


There's a zillion challenges of the form "I [do a thing to] the source code, you [do a thing to] the output!", like I double the source, you double the output! and I reverse the source code, you negate the output!. In this challenge you'll generalize that, writing a program that, given two functions x and y, will print a program p which prints some output o, with the property that x(p) prints y(o).

Task:

Your program (or function) should take two inputs, x and y, which can either be functions/lambdas, strings containing code, or some similar representation of a function in your language. You can assume these functions are pure: they have no side effects and do not depend on anything aside from their input. Other reasonable assumptions may be made based on your language's requirements, such as the input to x being a string of a certain length.

Your program should then print or return a program p, once again either as a pure lambda function (so it can't rely on x and y in the scope above it), a string representation of a program, function, or snippet, or some similar representation, such as writing an executable to a file. When p is run, it should take no input, and produce a deterministic value o. When x(p) is run, a second program will be produced, which, when run without input, should produce y(o) deterministically.

You may assume the data type of y(o) is the same as o, and make any other reasonable assumptions for your language. You may use any consistent data type for o, as long as it can hold more than 128 or so values (ints, floats, or strings would be preferred).

Sandbox:

This would be a very difficult challenge, and I'm not entirely sure what it would involve to answer or if it would even be possible to do so. I'm going to have to make some additional rules I think. maybe the inverse of x would be another input, that sort of thing. Feel free to suggest any ideas for rules to make this more possible and/or interesting, including across languages.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ what if x is, say, return ""? or something else disruptive like z=>return "exitprogram()"+z \$\endgroup\$ Jun 27 at 15:49
  • 1
    \$\begingroup\$ If x is an arbitrary function, this is impossible. Consider x being the identity function: p and x(p) are the same, so their outputs must be the same (since they must be pure and deterministic). For almost all y (in fact, all y except the identity function), this becomes impossible. You'd have to put some kind of very strong restriction on x for this to be doable, which I don't think can make it an interesting challenge. Either that, or allow solutions to be uncomputable (...cont'd) \$\endgroup\$
    – pxeger
    Jun 27 at 16:03
  • \$\begingroup\$ (...cont'd) (A "valid" but uncomputable solution could be of the form: generate every program p and compute x(p), and check that y(eval(p)) == eval(x(p))). Some more (less trivial) logic can be used to show that this is also impossible if y is an arbitrary function. \$\endgroup\$
    – pxeger
    Jun 27 at 16:03
  • 1
    \$\begingroup\$ @pxeger Yes, it's not possible with a number of xs and ys. I don't think restricting it so that it's possible makes it less interesting though. \$\endgroup\$ Jun 27 at 16:29
0
\$\begingroup\$

Interleavable programs (WIP)

Your task in this challenge is to create programs that can be interleaved. Submissions will be in the form of collections of programs. The score for each collection is 2 raised to the power of the number of programs in that collection, and your total score is the sums of the scores of all the submitted collections. Here are the rules for each collection:

  • There must be at least 2 programs in each collection
  • The programs in the collection must be ordered from 1 to \$n\$
  • The \$n\$th program must output the integers in the range \$(i-1)*n\$ to \$i*n\$. Output can be as a list or string with separators (the separator can be an empty string)
  • When your programs are interleaved, their output is also interleaved
  • Programs can be reused in other collections

Example answer, score = 12

Collection 1:

  1. abcdef
  2. 123
  3. jklom

Interleaved: a1jb2kc3ldoemf

Collection 2:

  1. abcdef
  2. 123

Interleaved: a1b2c3def

Questions for Meta

  • How do I make the description clearer? It's not great right now.
  • Is this a dupe?
  • Should the output be modified so it's easier? Maybe people can choose their own output?
  • Any way to improve the scoring? How do I prevent people gaming the score by posting answers with lots of collections of size 2? I was thinking about forcing all programs in all collections to be drawn from the biggest collection.
  • Is this even worth posting as a question?
\$\endgroup\$
0
\$\begingroup\$

Input program generating Fibonacci, output program generating Fibonacci

Challenge:

You will have to write program, which outputs program, that outputs single Fibonacci number. First program should output first element of sequence (0), second should output second element of sequence (1), etc. You can also write two input strings - first is input to your program when it is first launched. Second will be always input to the generated program. The next time your program is launched, it's input will be the program it generated previously.

Rules:

  • Your score is sum of length of program and input strings.
  • Your inputs can be something else than string (numbers, booleans). To get your score, treat them like strings. E.g. true have length 4, 123,false have length 9.
  • You can use two different languages for the programs, but solutions using single language are preferred.

Output sequence (A000045):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ...

Related

\$\endgroup\$
3
  • \$\begingroup\$ "write two input strings", maybe "take two input strings"? \$\endgroup\$
    – tsh
    Jul 11 at 6:02
  • \$\begingroup\$ "that outputs single Fibonacci number" do I required to output 0 for first outputted program, and 1 for the second one, ...? Or maybe I can always output 0 since it is a "Fibonacci number"? \$\endgroup\$
    – tsh
    Jul 11 at 6:04
  • \$\begingroup\$ @tsh I made edit to address your second comment. Also I think that "write" as well as "take" is correct. But I wanted to say that this challenge is not just about writing program which you submit to your answer, but you can also write the input which counts towards byte count and is also part of your answer. \$\endgroup\$
    – Jiří
    Jul 11 at 15:17
0
\$\begingroup\$

Make an ASCII art arrow

Given a size and direction (up, down, left, or right), you will create an ASCII art arrow.

Drawing it

For an arrow pointing up

For size \$s\$, there are \$2s\$ | characters in the center, with 1 _ character at the top. On the left of each of the top \$s\$ pipe characters, there is a / diagonally aligned with the arrow, and on the right side, the same but with backslashes.

Size 1:
 _
/|\
 |


Size 2:
  _
 /|\
/ | \
  |
  |

An arrow pointing down

Similar to an arrow facing up, it will have \$2s\$ (where \$s\$ is still the size) vertical | characters, with a hyphen below them. Starting from the bottom |, diagonally distribute slashes and backslashes on each side (only going up \$s\$ | characters).

Size 1:

 |
\|/
 -


Size 2:

  |
  |
\ | /
 \|/
  -

An arrow pointing left

Where \$s\$ is the size, there should be \$2s\$ hyphens going horizontally, with 1 | on the left of them. Starting from the leftmost hyphen, going up to the \$s\$th hyphen, diagonally distribute / and \ spreading out.

Size 1:

 /
|--
 \

Size 2:

  /
 /
|----
 \
  \

An arrow pointing right

This is pretty much an arrow pointing left, but inverted.

Where \$s\$ is the size, there should be \$2s\$ hyphens going horizontally, with 1 | on the right of them. Starting from the rightmost hyphen, going to the \$s\$th last hyphen, diagonally distribute / and \ spreading out.

Size 1:

 \
--|
 /

Size 2:

  \
   \
----|
   /
  /

Rules

  • As for the size, you may take any of \$n-1\$, \$n\$, \$n+1\$, or \$2n\$.
  • For the direction, you may use any four consistent values.
  • This is , so shortest code for each language wins.
  • Standard loopholes are forbidden.
  • Standard I/O rules apply.

Meta

  • Is this clear?
  • Is this too boring, or too similar to another challenge?
\$\endgroup\$
3
  • \$\begingroup\$ Related. \$\endgroup\$
    – Steffan
    Jul 12 at 18:04
  • \$\begingroup\$ Suggestion: make the arrows "pointy" (with ^v<>) - this may however make the challenge harder as would prevent simple reflection of up/down and right/left pairs. \$\endgroup\$
    – pajonk
    Jul 12 at 19:09
  • \$\begingroup\$ @pajonk I didn't do that because it looked fine on the up/down ones, but with left/right, it just looked really weird. \$\endgroup\$
    – Steffan
    Jul 12 at 20:08
0
\$\begingroup\$

Get string from CIGAR and reference

In the field of genomics, CIGAR (Concise Idiosyncratic Gapped Alignment Report) strings are sometimes used to indicate how a DNA sequence aligns to a reference sequence of DNA. CIGAR strings are sequences of <operation, length> pairs. An operation can be M, meaning "match", I, meaning "insert", or D, meaning delete. The length describes the number of times the operation is repeated1. (For our purposes, we'll assume a match means that both matched characters are the same -- i.e. an alignment match.)

Suppose we align string \$S\$ to reference string \$R\$, producing CIGAR string \$C\$. You can think of the CIGAR string \$C\$ as operations applied to \$R\$ to turn it into \$S\$. If we treat \$R\$ as a sequence of consumable tokens, then to get \$R\$:

  • Iterate through the pairs <operation, length> in \$C\$:
    • length times, repeat operation:
      • If operation is I, output a character different than the current token of \$R\$
      • If operation is D, consume the current token of \$R\$
      • If operation is M, consume and output the current token of \$R\$

(Note: You can assume that for any input CIGAR string, all tokens in \$R\$ will be consumed. In other words, the length of \$R\$ equals the number of M and D operations applied.)

For example, suppose we've aligned the DNA string ACAACTA to the reference ACTCAGTA as follows:

AC-AAC--TAC 
ACT--CAGTAC
MMDIIMDDMMM

This would be encoded as M2D1I2M1D2M3.

Another example:

-G-T--G-AT--GGCG-T
AGCTGCGCATAA-GC-A-
DMDMDDMDMMDDIDDIDI

Which is encoded as D1M1D1M1D2M1D1M2D2I1D2I1D1I1.

The challenge: Given the reference string \$R\$ and a CIGAR string \$C\$, output a string \$S\$ which would produce the CIGAR string \$C\$ when aligned to \$R\$. (There are obviously many cases where there are many possible strings which satisfy this condition -- you can output any one of them.)

Test cases:

\$R\$ \$C\$ \$S\$
AAA M3 AAA
AAA I3D3 CCC
AAA D3I3 CCC
AAA D1I1D1I2D1 CCC
AAA D3 (the empty string)
AAA M1D2I1 AC
ACTCAGTA M2D1I2M1D2M3 ACAACTA
AGCTGCGCATAAGCA D1M1D1M1D2M1D1M2D2I1D2I1D1I1 GTGATGGCGT

Standard loopholes are forbidden. Because this is , the shortest program wins.

1Paraphrased from https://www.ebi.ac.uk/about/vertebrate-genomics/software/exonerate-manual

Questions

The more obvious question would be "given reference \$R\$ and aligning string \$S\$, find the cigar string corresponding to the best possible alignment", but that probably has been done already, and I've already accidentally posted a duplicate question...

I almost certainly should explain alignment better, but I'm not sure how to do it.

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

Generate number set with conditions using n numbers

\$\endgroup\$
3
  • \$\begingroup\$ Is this the same as "generate \$T=\{T_1, ..., T_x\}\$, the minimum number of \$k\$-length subsets of \$\{1,...,n\}\$ such that every \$v\$-length subset of \$\{1,...,n\}\$ is a subset of some set in \$T\$"? \$\endgroup\$ Jul 29 at 20:31
  • \$\begingroup\$ @Adam yes It is same ? Has this been asked already? Or do you want me to change description to this ? \$\endgroup\$
    – 2FaceMan
    Jul 30 at 5:30
  • 1
    \$\begingroup\$ For future reference a quote from the main sandbox post above: "It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed." Some of the issues raised in the main site could have been caught and addressed here. \$\endgroup\$
    – pajonk
    Jul 30 at 18:04
0
\$\begingroup\$

Transform characters of your choice into "Hello, world!"

\$\endgroup\$
4
  • \$\begingroup\$ "takes character as input and outputs character", does it mean that the program output a single character? "fed into the program one by one", does it mean that the program take all 13 characters as input? If the program cannot store data between runs, how could it yield different output for same input? \$\endgroup\$
    – tsh
    Jul 11 at 6:00
  • 1
    \$\begingroup\$ @tsh you get to choose which 13 characters are input. so you could, for example, have it so that inputting each of "abcdefghijklm" outputs a character of "Hello, world!". Every other character input would just have to output a character, with no further restriction. \$\endgroup\$ Jul 11 at 12:47
  • 1
    \$\begingroup\$ I suspect in most languages it would be optimal to write a program which outputs its input, and use "Hello, world!" as the input, which isn't particularly interesting \$\endgroup\$ Jul 18 at 3:59
  • \$\begingroup\$ @CommandMaster This is why I chose that it have to be unique characters, so cat program can't be used anymore. (character o is there two times, character l three times) \$\endgroup\$
    – Jiří
    Jul 18 at 13:03
0
\$\begingroup\$

For Meta

This challenge is currently just a very undeveloped idea I had today! So I'm just dumping it here to start getting feedback and somewhere to leave my own thoughts and notes as I start this.

As this is in such a undeveloped form and I'm not sure when I'll have time to do it, other people are very much encouraged to develop this if they want!

I'm hoping to end up with something with a similar format to @trichoplax's Formic Functions - Ant Queen of the Hill Contest.

Notes

  • even a simple chess engine may be so complex that even expert golfing may have no effect on catching a better written engine in size
  • scoring seems very messy if you include game_length and function_length as these numbers could be all sorts of sizes
  • would checkers be a better/simpler game to do this with?
  • making it single language (javascript) would make it very easy to implement for me but would make golfing less interesting?

The Code Golf Chess Invitational

I have developed a simple chess interface (to be written) that will:

  1. provide board state to your function
  2. wait for your functions move
  3. verify your move
    • invalid moves will result in a loss
  4. make the move
  5. repeat for the opponent
  6. and repeat until there is a winner
  7. then score both functions

The score

The score of each function will be determined by the length of each function and the number of moves the game lasted. With higher scores being worse!

  • Winners score will be 1 * length_of_program
  • Losers score will be game_length * length_of_program
  • Losing by invalid move score will be (game_length)^2 * length_of_program

(Scoring very much to be revised but ideally I want to encourage short programs, encourage winning, and absolutely discourage invalid moves (random playing))

Your function

  • MUST NOT query other sites/libraries/etc
    • it could include an entire library if you wished, but that would obviously be a very long function
  • should take a 2d array as input of the board state, [[a1, a2 ... a8], [b1 ... h8]]
  • return a chess move in chess notation
  • warnings (and errors?) are fine as long as the program still returns a move
  • normal other restrictions apply

You, yourself

  • Please provide assistance in getting your function running on the GitHub site!

(this needs work because whilst I'm sure I could get many common languages (esp scripting languages) working I'm not sure how well I'd do with some of the more golf-y/compiled languages)

Tournament

The initial tournament would be a continuous round robin of all current submissions with each functions running score an average of each score each game.

Then a final day, where every function competes against every function x times. This would decide the "winner" of the competition and the accepted answer tick.

Then just for fun a seeded knockout tournament (based on the final score) to decide who had the best chess program. (Maybe a bounty award for this)

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think you should make winners score 0 and losers (including invalid moves) length_of_program+10 or something similar. Because currently the best strategy is to lose game at beginning by invalid move. Anyway, if you decide my idea of scoring isn't good enough, then it feels weird to punish losers for long games - I expect that longer games are harder and shorter games are simpler, so the scoring should be opposite. \$\endgroup\$
    – Jiří
    Aug 4 at 15:59
0
\$\begingroup\$

Implement Bloom filter insertion

A Bloom filter is a probabilistic data structure that is used to determine whether an element is in a set in a fixed number of bits. It consists of:

  1. a bit array \$B\$ of fixed size \$m\$, initialized as all \$0\$s, and
  2. \$k\$ different hash functions \$h_1,\ldots,h_k\$ which each map any element to some value \$v \in 0,\ldots,m-1\$.

To insert element \$s\$ into the set, set \$B[h_i(s)]\$ to \$1\$ for each hash function \$h_i\$.

To check if element \$s\$ is in the set, check the value of \$B[h_i(s)]\$ for each hash function \$h_i\$. If they are all \$1\$, return true; otherwise return false.

For example, suppose we start with bit array of size 5:

0 0 0 0 0

We also define hash functions \$h_1(s) = s\bmod m, h_2(s) = (s^2)\bmod m\$. To insert value \$13\$, We calculate the indices to change: $$i_1 = h_1(13) = 13\bmod 5 = 3,\\ i_2 = h_2(13) = (13^2)\bmod 5 = 4$$ So we set \$B[3]\$ and \$B[4]\$ to \$1\$:

0 0 0 1 1

To check if \$13\$ is in the set, we look if \$B[3]\$ and \$B[4]\$ are both \$1\$.

The challenge

You should implement the insertion part of a Bloom filter. Take in three inputs: two positive integers \$m\$ and \$k\$, and a series of non-negative integers \$S=\{s_1, \ldots, s_n\}\$. Output the bit array of the Bloom filter of size \$m\$ with all the elements of \$S\$ added using \$k\$ hash functions, with any two distinct values substituting for \$1\$ and \$0\$.

You can choose any \$k\$ hash functions as long as they have uniformly distributed output and are not perfectly correlated (probably the wrong term for this). In other words:

  • Over all non-negative integers \$\{s\}\$, the probability of \$h_i(s)=v\in\{0,\ldots,m-1\}\$ is \$\frac1m\$.
  • For all pairs of functions \$(h_i,h_j)\$, there is not a mapping between the output of \$h_i\$ and the output of \$h_j\$. For example, you couldn't use \$h_1(s) = s\bmod m, h_2(s) = (s+1)\bmod m,\$ because you can perfectly determine the output of \$h_2\$ from the output of \$h_1\$.

(Ideally, these functions should be independent, but that's not a practical request.)

Examples

TODO

Questions

I could ask for both insertion and value checking, but I don't want to overcomplicate this.

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

All permutations of range from \$1\$ to \$n\$

Given a positive input \$n\$, output all permutations of either \$\{0,1,\ldots,n\}\$ or \$\{1,2,\ldots,n\}\$.

Examples

Outputting permutations of \$\{1,2,\ldots,n\}\$.

Input Output
1 [(1)]
2 [(1, 2), (2, 1)]
4 [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]

Standard loopholes are forbidden. The shortest code wins.

Questions

I was looking for this challenge, but I couldn't find it posted anywhere. Maybe because it's too derivative of a simple "output all permutations" challenge?

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

Hello, World! hashing

Implement a one-way hashing function that generates arbitrary strings which have a chance (obviously input dependent) of producing at least any of the printable ASCII characters when provided an input of at least 2 characters. This can be any mechanism you choose and could always output a fixed length if desired, however when your source code is used as input, the resultant output must be Hello, World!.

Rules

  • The input string will always be 2 characters or more (meaning your code must be at least two characters).
  • There are no other special requirements for any other input strings.
  • The output should not be exactly the same as the input (this might be unavoidable in some scenarios with well-crafted input, but you can't just output your input if the code Hello, World!, by some magic, in your language performs some sort of hashing).
  • It should be feasible to get at least any of the printable ASCII characters as output. You are however not limited to printable ASCII output and may output any combination of bytes (e.g. unprintables, UTF-8 sequences)
  • All characters of the input string should be taken into account when generating strings, not just the first 13 and should affect the output.

For meta

I'd really like to encourage answers that aren't a condition that just compares input with source and outputs Hello, World! in that instance, but as pointed out by @pajonk it's a non-observable requirement.

\$\endgroup\$
9
  • \$\begingroup\$ I think you can use tags code-golf, hello-world and restricted-source. Can you also explain what does "strings consisting of at least (but not limited to) the printable ASCII" mean? (That some strings have to contain printable characters or all strings have to contain printable characters?) Also does full input string have to be used to calculate hash? I expect some people might want to use just fixed part of input string to make this task easier. \$\endgroup\$
    – Jiří
    Aug 2 at 16:10
  • 2
    \$\begingroup\$ Suggested tag: self-referential. Be careful with non-observable requirements (like you must not have a special condition), as they are discouraged. Also, you may define what does most inputs should result in different output mean exactly (or drop it), as this may be considered too vague. \$\endgroup\$
    – pajonk
    Aug 3 at 7:12
  • \$\begingroup\$ @Jiří My intention with that wording is that the output you generate must at least have the possibility for any character in the printable ASCII range to be included, but may also output unprintables or higher byte value unicode chars for instance. The full input string must also be used, yes. So changing a character at the end of the string should change the value returned. I'll clarify that. Also, not entirely sure on restricted-source, but I'll check the wiki, thank you! \$\endgroup\$ Aug 3 at 12:24
  • \$\begingroup\$ @pajonk Yeah, that's a good point. I guess I didn't want an arbitrary hashing algorithm with a if input == source condition (which I think would be considerably easier). Good point about the wording on most inputs I'll clarify along with Jiří's suggestion of ensuring all characters are used and can affect the output, hopefully that covers that off. I'll look at self-referential too. Thank you! \$\endgroup\$ Aug 3 at 12:27
  • \$\begingroup\$ @pajonk I can't think of a way to make an observable requirement to avoid the simpler solution which makes me inclined to remove this as I think it trivialises the problem. Any idea on how to enforce that without having this blacklisted? \$\endgroup\$ Aug 3 at 12:34
  • \$\begingroup\$ @DomHastings remember that simple comparison input==source is not so simple, as requires a modified version of a quine. This may or may not be shorter than other possible approaches. \$\endgroup\$
    – pajonk
    Aug 3 at 12:45
  • \$\begingroup\$ Also I was thinking how I would write answer for this and came up with following idea: Sum all characters on input and then add this sum to ASCII codes of individual characters of string "Hello, World!" (%256). Would this answer be fine? \$\endgroup\$
    – Jiří
    Aug 3 at 13:08
  • \$\begingroup\$ @Jiří yeah, absolutely! \$\endgroup\$ Aug 7 at 13:26
  • \$\begingroup\$ @pajonk I guess so, I feel like modified quines aren't that interesting sometimes... But you're right, probably not trivial in every language. I guess the kinda of answer is love to see is a generic mechanism that is calculated to, based on the code as input, the exact string required, but that might be a big request! It's an interesting problem (to me at least) as it felt easier than I've found it upon trying to execute it! \$\endgroup\$ Aug 7 at 13:29
0
\$\begingroup\$

Generate a Kirkman triple system

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

Program a compiler compiler

Write a program, function, or likewise that takes in a BNF-like grammar specification(see below) and outputs a program or function in a language of your choice that takes strings as input and returns truthy if that string is parseable with the specified grammar, and false otherwise.

Meta-language:

The input to your program will consist of a number of bnf-like rules. Each definition will be on its own line, and will consist of a name (string of 1 or more characters [a-z0-9]), followed by the symbol ::= followed by a string of symbols(terminal and non terminal), terminals consist of [a-zA-Z0-9() ]. Nonterminals are denoted with a < followed by a string of characters [a-z0-9] followed by >; that string of characters refers to another definition. Each definition may have multiple alternatives, separated by |. Alternatives should be matched left to right. The first line of the input will share this same form, except that it will not have the name of the definition or the ::=. This is the "top-level" definition that the input to the outputted program will attempt to be matched against.

Input grammars will never contain left-recursion (ie. it will never be the case that there will be a rule of the form a::=<a>). You may additionally assume that your generated program will only be given as input strings that contain only those characters comprising valid terminal symbol([a-zA-Z0-9() ]). Additionally, your compiler-compiling program only needs to handle valid definitions.

Examples:

The following should be handled appropriately by your program:

binaryliteral
binaryliteral::=0<binaryliteral>|1<binaryliteral>|0|1

This means that the generated program should return truthy for any strings that match the definition of a binary literal, which is either the character 0 or 1 followed by a binary literal, or just 0 or 1. This would recognize strings

quantexpr
quantexpr::=forall <var>(<expr1>)|exists <var>(<expr1>)
expr1::=<expr0> and <expr1>|<expr0> or <expr0> |not <expr1>|<expr0>
expr0::=<var>|(<expr1>)
var::=x|y|z

and you do not need to handle the following:

x:=1
expr
expr::=x|<expr> plus <expr>

As usual, this is code-golf, so the shortest program per (implementation, output language) pair wins!

\$\endgroup\$
3
  • \$\begingroup\$ This could use a bit of cleanup but I'm totally behind this idea, so +1. Note: i think your terminal string regex is wrong, +-* expresses a range. in general i think it'd be worth considering simplifying what terminals are allowed, but thats just my onpinioin \$\endgroup\$ Aug 15 at 15:06
  • \$\begingroup\$ @thejonymyster good catch on that regex; I'll fix that. Is there anything else that needs to be changed pursuant to "cleaning up"? \$\endgroup\$
    – Benji
    Aug 15 at 16:57
  • \$\begingroup\$ sorry for the nondescriptive wording on my part; I just think the meta language description could be broken down into smaller sections, maybe with a small worked-out example or two. As is, it's fairly clear but just a bit densely packed. Additionally, I think you should link to something (maybe wikipedia) about BNF, for those entirely unfamiliar. :-) \$\endgroup\$ Aug 15 at 18:13
0
\$\begingroup\$

smallest number of steps for a knight in chess

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ Aug 20 at 1:07
0
\$\begingroup\$

Add numbers as fairly as possible

Given an array of integers \$X\$ and an array of positive integers \$A\$, figure out how to add the values in \$A\$ to the values in \$X\$ such that the variance of the updated values is as small as possible. (You can add more than one value from \$A\$ to a given value in \$X\$.)

[Explanation of variance]

If there are multiple solutions, you can output any of them. Output in any reasonable format.

Example

Suppose \$X = [4,5,6]\$ and \$A=[1,2]\$. The "most fair" way to distribute the value \$1\$ to \$4\$ and \$2\$ to \$5\$, making the updated array \$X' = [6,6,6]\$, which has a variance of \$0\$. Therefore, you should output something like [[2],[1],[]] or {4:[2],5:[1]}.

Test Cases

[TODO]

Questions

I am almost certain a question like this has been done before, which is why I'm not putting much effort into this post.

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

Contrasting Colors

When designing a website or poster or book it's important to make the graphical elements be distinct. A common mistake is to choose colors to similar to eachother. We must prevent this!

The goal of this challenge is simple: Given a initial color and a number of colors to generate, generate N colors that each have maximal contrast to each of the previous colors.

Contrast is defined as the sum of absolute differences. The contrast of a new color is the minimum of the distances to all previous colors. You do not need to consider gamma. Colors are a 3 tuple with each value a integer ranging from 0 to 255.

You must use a greedy algorithm. AKA you shouldn't consider the number or even existence of colors afterwards, just colors before. This is because in the design each subsequent color will be used significantly less.

In some cases, multiple choices are available. In this case you may pick any. Thus your results might not look the same as my test cases but still be valid.

You may chose whether to include the initial value in the output or not.

This is code golf, shortest answer wins.

Test cases

{
    [(255,255,255),5]: [(255, 255, 255), (0, 0, 0), (0, 127, 255), (63, 255, 64), (191, 0, 191), (254, 128, 0)],
    [(255,0,128),5]: [(255, 0, 128), (0, 255, 0), (0, 64, 255), (191, 255, 223), (32, 0, 32), (192, 128, 0)],
    [(128,128,128),10]: [(128, 128, 128), (0, 0, 0), (0, 255, 255), (255, 0, 255), (255, 255, 0), (32, 32, 223), (32, 223, 32), (223, 32, 32), (223, 223, 224), (0, 81, 111), (81, 96, 15)],
    [(7,91,7), 5]: [(7, 91, 7), (255, 255, 255), (89, 0, 255), (255, 0, 44), (0, 211, 217), (173, 255, 0)]
}
\$\endgroup\$
2
  • \$\begingroup\$ Do we need to include the initial color in the output? The text suggests no, but the test-cases do include it. Also, are the color values required to be integer? \$\endgroup\$
    – pajonk
    Aug 29 at 12:38
  • \$\begingroup\$ You may or may not include the initial value, your choice. Colors must be integers. I'll clarify \$\endgroup\$
    – mousetail
    Aug 29 at 12:42
0
\$\begingroup\$

The least amount a steps a chess pice can reach a position

I have previously posted a challange: smallest number of steps for a knight in chess. Now I would like to go a step further by adding the possibility to choose you piece.

If you place a pice on any square of a chessboard, what is the smallest amount of steps to reach every possible position?

Rules

  • It is an 8 by 8 board.
  • The given input is a coordinate (x,x) and the chosen piece. Explain in the answer how to input the piece of choice.
  • The piece starts at an arbitrary position, taken as input.
  • The pawn can not start at the bottom row, and can not move 2 steps (like when in the startposition).
  • point '.' will be placed if a pice cannot reach the square.

Example
With input 1, 0 for a knight, we start by putting a 0 in that position:

. 0

From her on we continue to fill the entire 8x8 board. For a knight the output will look like follow

3 0 3 2 3 2 3 4
2 3 2 1 2 3 4 3
1 2 1 4 3 2 3 4
2 3 2 3 2 3 4 3
3 2 3 2 3 4 3 4
4 3 4 3 4 3 4 5
3 4 3 4 3 4 5 4
4 5 4 5 4 5 4 5

For a pawn with input (1, 7) the output will look like follow

. 6 . . . . . . 
. 5 . . . . . . 
. 4 . . . . . . 
. 3 . . . . . . 
. 2 . . . . . . 
. 1 . . . . . . 
. 0 . . . . . . 
. . . . . . . . 

In the examples, I start counting from zero but it does not matter if you start from or one.

Challenge The pattern printed for a pice, as short as possible, in any reasonable format.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I'd recommend allowing the piece indicator to be any 6 distinct values, rather than requiring them to be 0,1,...,5 in a certain order. \$\endgroup\$ Aug 30 at 16:36
  • 2
    \$\begingroup\$ Also, a few typos: "stap" (step), "you pice" (your piece), "pice" (piece), "nummerate" (enumerate) \$\endgroup\$ Aug 30 at 16:39
0
\$\begingroup\$

Strategy: The cunning cousin witch

The wizard has a cunning cousin who is a witch. She looks down on the wizard, regarding him and his puzzles as mathematically naive. On reading his latest puzzle, she scorned him for always asking discrete problems with what she (unfairly) characterises as simple solutions, where the real, proper question should be continuous. To prove her point she poses the following version of the wizard's puzzle. (He reluctantly permits the partial plagiarism.)

Consider the following setup. An evil witch has a number line stretching from 0 to 10 which is hidden from you. Also hidden from you she chooses a random integer \$x \in \{0, \dots, 10\}\$ and places that many points onto the number line uniformly at random. To be more precise, she places each of the \$x\$ points independently and uniformly at random onto the number line. Your task is to prove that \$x = 10\$ and if you do the witch will grant you what she promises is a much better wish than what her cousin can provide.

In this game, you can at each step choose a floating point number \$y\$ and the witch will tell you the number of points on the number line with value less than or equal to \$y\$.

However the witch, being at least as evil as her cousin, will not let you choose a number larger than \$9\$. This might still be OK as you might still find 10 points and in fact the only way to be granted the wish is to have found all 10 points with values 9 or less.

The cost for choosing a floating point number \$\ell\$ is \$2^{\ell}\$ dollars. At any point, you can choose to give up on this set of points and get her to start the whole process again (with a new random \$x\$). Of course, if you choose the number 9 and you still have not found 10 points you have no choice but to give up and start again. But you might want to give up earlier too. Sadly you never get any money back so your costs just carry on building.

Your goal is to devise a strategy that will get you the wish at the minimum expected cost. You should report your mean cost.

Testing

Once you have chosen your strategy, you should run it until you get the wish 10,000 times and report the mean cost. If two answers have the same strategy, the one posted first wins. If two strategies have similar mean costs you may need to test it 100,000 or even more times to tell the difference. Of course if you can directly compute the expected cost, all the better.

Input and output

There is no input in this challenge. The output is just the mean cost to get a wish. To test your code you will need to implement both the witch and your strategy.

What's a naive score?

If you just choose 9 each time then it will take you \$\frac{1}{\frac{1}{11} \cdot \frac{9}{10}^{10}} \approx 31.5\$ tries to find 10 points. This will cost you approximately \$16152.4\$ dollars. How much better can you do?

\$\endgroup\$
2
  • \$\begingroup\$ I think it's more elegant if the values instead range from 0 to 1 -- the situation is exactly the same except that the values are scaled down. \$\endgroup\$ Aug 31 at 17:02
  • \$\begingroup\$ @Adam I thought about that. The problem is that \$2^9=512\$ is a nicer number than \$2^{0.9} \approx 1.87\$. \$\endgroup\$
    – graffe
    Aug 31 at 17:09
0
\$\begingroup\$

Persistence of a number

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

Set of all sets

Write a program or function which outputs all sets with a finite number of elements - but including sets that contain themselves (directly or indirectly).

These recursive sets will be represented using a system similar to De Bruijn indices: an element of a set which is a reference to an outer enclosing set will be represented by a positive integer indicating how far "outside" that set is. For example, the set that contains itself, \$ s = \{s\} = \{\{\{\dots\}\}\} \$, is represented by {1}.

Note that some of these representations are equivalent (represent the same actual set). For example, {{2}} directly represents \$ s = \{\{s\}\} = \{\{\{\dots\}\}\} \$, but this is equal to \$ s = \{s\} \$, and so {1} and {{2}} (and {{{3}}} etc.) are all equivalent.

Here are a few more examples of this representation:

  • \$ s = \{\{\}, s\} = \{\{\},\{\{\},\{\{\},\dots\}\}\}\$ = {{}, 1} (or {{}, {{}, 2}} etc.)
  • \$ s = \{\{\{\}\}, \{s\}\} = \{\{\{\}\}, \{\{\{\{\}\}, \{\dots\}\}\}\} \$ = {{{}}, {2}} (or {{{}}, {{{{}}, {4}}}} etc.)

Rules

Your sequence of sets may be in any order, as this is an question. However, your sequence may never contain the same set more than once. (This includes the same set represented in different ways, e.g. {1} and {{2}}.)

  • As with standard challenges, you may choose to either:
    • Take an input n and output the nth term of the sequence
    • Take an input nand output the first n terms
    • Output the sequence indefinitely, e.g. using a generator
  • You may use 0- or 1-indexing
  • This is , so the aim is to minimise your program's length in bytes

Meta

  • I really don't think I've done a good job of explaining this challenge; please feel free to edit it to be clearer
  • Does this representation have an existing name?
  • Other potentially interesting challenges involving this representation could be: (Which of these would make for good challenges?)
    • Is this representation fully simplified? (e.g. yes for {1}, no for {{2}})
    • Simplify this representation (e.g. {{2}} -> {1})
    • Do these two representations represent the same set? (e.g. {1} = {{2}}; {{}}{1})
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You haven't defined when two sets are equal. Are {{1}} and {1} equal? How about {1} and {1,{2}}? You probably should pick a consistent set theory that denies the axiom of regularity and work from there. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 20 at 17:44
0
\$\begingroup\$

(Inspired by https://codegolf.meta.stackexchange.com/a/25136/91213)

Quarter Precision Floating Point Numbers

We all love our floating point formats, floats and doubles. People who work in embedded may have used a even shorter format: The half precision floating point. However, what if you want a even smaller format? I present the quarter precision floating point number.

It is defined like this:

  • 1 bit: s The sign. 1 is negative, 0 is positive.
  • 3 bits: e The exponent -4. So 000 is 2**-4, 100 is 2**0 and 111 is 2**3
  • 4 bits: f The fraction f. A leading 1 bit is assumed.

Overall formula is (2-s*2)*2**(e-4)*f|16.

There is no 0, infinity, -infinity, NaN, or any subnormals.

Task

Your task is to produce a pair of programs, one to convert from quarters to floats and one to convert from floats to quarters. Your score is the sum of the length of both programs. Input will always be exactly representable.

Test Cases

These is a complete set of possible input values.

Quarters as:    Float Equivalent
bin      dec    
00000000 000    0.0625
00000001 001    0.06640625
00000010 002    0.0703125
00000011 003    0.07421875
00000100 004    0.078125
00000101 005    0.08203125
00000110 006    0.0859375
00000111 007    0.08984375
00001000 008    0.09375
00001001 009    0.09765625
00001010 010    0.1015625
00001011 011    0.10546875
00001100 012    0.109375
00001101 013    0.11328125
00001110 014    0.1171875
00001111 015    0.12109375
00010000 016    0.125
00010001 017    0.1328125
00010010 018    0.140625
00010011 019    0.1484375
00010100 020    0.15625
00010101 021    0.1640625
00010110 022    0.171875
00010111 023    0.1796875
00011000 024    0.1875
00011001 025    0.1953125
00011010 026    0.203125
00011011 027    0.2109375
00011100 028    0.21875
00011101 029    0.2265625
00011110 030    0.234375
00011111 031    0.2421875
00100000 032    0.25
00100001 033    0.265625
00100010 034    0.28125
00100011 035    0.296875
00100100 036    0.3125
00100101 037    0.328125
00100110 038    0.34375
00100111 039    0.359375
00101000 040    0.375
00101001 041    0.390625
00101010 042    0.40625
00101011 043    0.421875
00101100 044    0.4375
00101101 045    0.453125
00101110 046    0.46875
00101111 047    0.484375
00110000 048    0.5
00110001 049    0.53125
00110010 050    0.5625
00110011 051    0.59375
00110100 052    0.625
00110101 053    0.65625
00110110 054    0.6875
00110111 055    0.71875
00111000 056    0.75
00111001 057    0.78125
00111010 058    0.8125
00111011 059    0.84375
00111100 060    0.875
00111101 061    0.90625
00111110 062    0.9375
00111111 063    0.96875
01000000 064    1.0
01000001 065    1.0625
01000010 066    1.125
01000011 067    1.1875
01000100 068    1.25
01000101 069    1.3125
01000110 070    1.375
01000111 071    1.4375
01001000 072    1.5
01001001 073    1.5625
01001010 074    1.625
01001011 075    1.6875
01001100 076    1.75
01001101 077    1.8125
01001110 078    1.875
01001111 079    1.9375
01010000 080    2.0
01010001 081    2.125
01010010 082    2.25
01010011 083    2.375
01010100 084    2.5
01010101 085    2.625
01010110 086    2.75
01010111 087    2.875
01011000 088    3.0
01011001 089    3.125
01011010 090    3.25
01011011 091    3.375
01011100 092    3.5
01011101 093    3.625
01011110 094    3.75
01011111 095    3.875
01100000 096    4.0
01100001 097    4.25
01100010 098    4.5
01100011 099    4.75
01100100 100    5.0
01100101 101    5.25
01100110 102    5.5
01100111 103    5.75
01101000 104    6.0
01101001 105    6.25
01101010 106    6.5
01101011 107    6.75
01101100 108    7.0
01101101 109    7.25
01101110 110    7.5
01101111 111    7.75
01110000 112    8.0
01110001 113    8.5
01110010 114    9.0
01110011 115    9.5
01110100 116    10.0
01110101 117    10.5
01110110 118    11.0
01110111 119    11.5
01111000 120    12.0
01111001 121    12.5
01111010 122    13.0
01111011 123    13.5
01111100 124    14.0
01111101 125    14.5
01111110 126    15.0
01111111 127    15.5
10000000 128    -0.0625
10000001 129    -0.06640625
10000010 130    -0.0703125
10000011 131    -0.07421875
10000100 132    -0.078125
10000101 133    -0.08203125
10000110 134    -0.0859375
10000111 135    -0.08984375
10001000 136    -0.09375
10001001 137    -0.09765625
10001010 138    -0.1015625
10001011 139    -0.10546875
10001100 140    -0.109375
10001101 141    -0.11328125
10001110 142    -0.1171875
10001111 143    -0.12109375
10010000 144    -0.125
10010001 145    -0.1328125
10010010 146    -0.140625
10010011 147    -0.1484375
10010100 148    -0.15625
10010101 149    -0.1640625
10010110 150    -0.171875
10010111 151    -0.1796875
10011000 152    -0.1875
10011001 153    -0.1953125
10011010 154    -0.203125
10011011 155    -0.2109375
10011100 156    -0.21875
10011101 157    -0.2265625
10011110 158    -0.234375
10011111 159    -0.2421875
10100000 160    -0.25
10100001 161    -0.265625
10100010 162    -0.28125
10100011 163    -0.296875
10100100 164    -0.3125
10100101 165    -0.328125
10100110 166    -0.34375
10100111 167    -0.359375
10101000 168    -0.375
10101001 169    -0.390625
10101010 170    -0.40625
10101011 171    -0.421875
10101100 172    -0.4375
10101101 173    -0.453125
10101110 174    -0.46875
10101111 175    -0.484375
10110000 176    -0.5
10110001 177    -0.53125
10110010 178    -0.5625
10110011 179    -0.59375
10110100 180    -0.625
10110101 181    -0.65625
10110110 182    -0.6875
10110111 183    -0.71875
10111000 184    -0.75
10111001 185    -0.78125
10111010 186    -0.8125
10111011 187    -0.84375
10111100 188    -0.875
10111101 189    -0.90625
10111110 190    -0.9375
10111111 191    -0.96875
11000000 192    -1.0
11000001 193    -1.0625
11000010 194    -1.125
11000011 195    -1.1875
11000100 196    -1.25
11000101 197    -1.3125
11000110 198    -1.375
11000111 199    -1.4375
11001000 200    -1.5
11001001 201    -1.5625
11001010 202    -1.625
11001011 203    -1.6875
11001100 204    -1.75
11001101 205    -1.8125
11001110 206    -1.875
11001111 207    -1.9375
11010000 208    -2.0
11010001 209    -2.125
11010010 210    -2.25
11010011 211    -2.375
11010100 212    -2.5
11010101 213    -2.625
11010110 214    -2.75
11010111 215    -2.875
11011000 216    -3.0
11011001 217    -3.125
11011010 218    -3.25
11011011 219    -3.375
11011100 220    -3.5
11011101 221    -3.625
11011110 222    -3.75
11011111 223    -3.875
11100000 224    -4.0
11100001 225    -4.25
11100010 226    -4.5
11100011 227    -4.75
11100100 228    -5.0
11100101 229    -5.25
11100110 230    -5.5
11100111 231    -5.75
11101000 232    -6.0
11101001 233    -6.25
11101010 234    -6.5
11101011 235    -6.75
11101100 236    -7.0
11101101 237    -7.25
11101110 238    -7.5
11101111 239    -7.75
11110000 240    -8.0
11110001 241    -8.5
11110010 242    -9.0
11110011 243    -9.5
11110100 244    -10.0
11110101 245    -10.5
11110110 246    -11.0
11110111 247    -11.5
11111000 248    -12.0
11111001 249    -12.5
11111010 250    -13.0
11111011 251    -13.5
11111100 252    -14.0
11111101 253    -14.5
11111110 254    -15.0
11111111 255    -15.5
\$\endgroup\$
1
  • \$\begingroup\$ f = lambda x:(1-((x&128)>>7)*2)*(16|(x&15))*2.0**(((x&(16|32|64))>>4) - 8) \$\endgroup\$
    – mousetail
    Sep 22 at 13:39
0
\$\begingroup\$

An Optimally Suboptimal Solution

You have grown disillusioned by finding optimal policies for heavy-tailed distributions and their "skew you" attitudes. You decide that for this challenge you are putting your foot down and refusing to optimize your policy further if it means having unbalanced errors. In fact, you're so focused on balance that you will only consider median errors - it's the principle of the thing.

The Challenge

Generate a policy that searches for hidden points on a line segment, \$L\$, where \$L\$ is the interval \$[0, 1]\$. The number of hidden points on \$L\$ is randomly chosen from the set \$\{0, 10\}\$. The position of each point, \$p\$, (if there are any) is drawn randomly from the uniform distribution on \$\{0, 1\}\$. The points are indistinguishable.

The problem is episodic. In each episode you search the line according to your policy. At each step in the episode you may continue to search the line, or you may reset.

To search the line

  1. Choose \$x \in[0, 0.9]\$
  2. Accrue a cost of \$2^x\$
  3. Discover all points where \$0 \leq p \leq x\$

To reset

  1. Generate a new line segment
  2. Draw a new number of hidden points to place on the line segment
  3. If there are any hidden points, place them on the line segment

An episode ends when your policy has discovered 10 hidden points on the interval \$[0, 0.9]\$.

Note: Your policy may not use information about the number of hidden points, nor their locations. When resetting, you do not keep any points you have previously found, but you do keep all costs accrued.

This setup is adapted from @graffe's Cunning Cousin Witch problem.

Scoring

Define a false negative to be when a policy chooses to reset a line segment and there were 10 hidden points on the interval \$[0, 0.9]\$, i.e. it was possible to complete the episode but the policy resets instead.

Define a false positive to be when a policy searches the entire interval \$[0, 0.9]\$, and there were fewer than 10 hidden points on the interval \$[0, 0.9]\$, i.e. it was not possible to complete the episode but the policy searches the entire available line segment.

Your policy's score is the median absolute difference between the number of false negatives and false positives your policy incurs over one million episodes. The score should be minimized.

$$\text{Score} = median(\lvert FN - FP \rvert)$$

Where \$FN\$ and \$FP\$ are vectors of length one million, and the nth element of each vector is the number of false negatives / positives the policy made in episode n.

If two policies have the same score, the one with the lower median cost from searching lines will rank higher.


Meta

I'm hoping to encourage some custom optimization methods with this one by asking for solutions that are not optimal with respect to the cost function, and by making the objective multi-criteria (because the tie-breaking cost of searching is a function of FN and FP). I think that the way points are discovered prevents optimizing with the cost = x from being equivalent to solving this one, but I haven't exhaustively tested it.

I'd especially appreciate feedback on whether this is an interesting / productive variation on the original version, and whether or not the optimization task is equivalent to a trivial formulation.

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

Implement the Hamming algorithm

Hamming error correction is a form of linear error-correction code which can detect and repair small errors in its input. Your job is to implement a program that, given an input of a sequence of bytes, encodes them using Hamming error correction and outputs the results.

The algorithm

Taken from Wikipedia, with some slight modifications

  1. Number all of the bits, starting from 1
  2. Write these numbers in binary
  3. Every bit position that is a power of 2 (has only one 1 bit in its binary position) is a parity bit, with the remaining bits being data bits.
  4. Set every parity bit with the values of every data bit where the bitwise AND of the parity bit's position and the data bit's position is nonzero

You may choose any parity (even or odd) but must state it in your answer.

Examples

These will use hexadecimal to represent the data.

0x1234 -> 0x2a3a1
0x4321 -> 0x8b28e
0xbadf00d -> 0x2f5be8064
\$\endgroup\$
1
0
\$\begingroup\$

Cut along the lines

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

Which weekday was it?

\$\endgroup\$
5
  • \$\begingroup\$ what span of years do we have to account for \$\endgroup\$ Oct 3 at 13:40
  • \$\begingroup\$ only between 2000 to 2022. if you want it widened, i can do so \$\endgroup\$ Oct 3 at 13:40
  • \$\begingroup\$ I think I'll leave out the suggested algorithm as people will use their own ideas for sure. However, I'll add a sentence discouraging built-ins - sth like "if you're using a built-in, consider adding a non-buit-in approach as well". Regarding the year span, i think a narrow one is a good idea, as we avoid problems with changing calendars etc. \$\endgroup\$
    – pajonk
    Oct 5 at 6:45
  • \$\begingroup\$ Since you posted the question, the convention is to remove the content here and replace it with a link to the code golf post. \$\endgroup\$ Oct 5 at 14:30
  • \$\begingroup\$ Oh right, forgot that \$\endgroup\$ Oct 5 at 14:42
0
\$\begingroup\$

Best Iterated Prisoner's Dilemma Move

Introduction

In the prisoner's dilemma, two partners in crime are being interrogated, and have the choice to either betray their partner or stay silent.

  • If both prisoners betray each other, they both get 2 years in prison.
  • If neither betrays (both stay silent), they both get 1 year in prison.
  • If only one betrays and the other stays silent, then the betrayer gets no prison time, but the other gets 3 years in prison.

In the iterated version of the dilemma, this situation is repeated multiple times, so the prisoners can make decisions based on the outcomes of previous situations.

Challenge

Imagine that you are a player participating in this dilemma against an opponent.

Your opponent is described by a function \$f: M \mapsto m\$, where \$m = \{s,b\}\$ is the set of "moves" player can make (stay silent or betray) and \$M = [(m_{1o}, m_{1p}), (m_{2o}, m_{2p}), \ldots]\$ is a list of all the previous moves that your opponent and you made. In other words, given all the moves made in the game so far, the function outputs a new move.

Your code should take as input \$f\$ and some number \$n\$ and return a list \$[m_{1p}, m_{2p}, \ldots, m_{np}]\$ describing all the moves which you should make to minimize your overall punishment over \$n\$ iterations of the prisoner's dilemma.

You can use any two distinct symbols to represent the two moves, and the input format for the function is flexible (e.g. it could also take in two different lists for the opponents and player's previous moves.)

Standard loopholes are forbidden. Since this is , the shortest code wins.

Examples

(All the code examples will be in JavaScript; I will use 0 for the "stay silent" move and 1 for the "betray" move.)

If your opponent always stays silent, i.e. they are defined by the function

opponentFunc = (opponentMoves, playerMoves) => 0

Then it is in your best interest to always betray, so

playerFunc(opponentFunc, 1) //=> [1], reward=0
playerFunc(opponentFunc, 3) //=> [1,1,1], reward=0

Suppose your opponent employs the "tit for tat" strategy: stay silent on the first move, then does whatever the player did on the previous move. In other words, they are defined by the function

opponentFunc = (opponentMoves, playerMoves) => (playerMoves==[]) ? 0 : playerMoves[playerMoves.length-1]

In that case the best actions to take are to stay silent until the final turn, where you betray; i.e.

playerFunc(opponentFunc, 1) //=> [1], reward = 0
playerFunc(opponentFunc, 3) //=> [0,0,1], reward = -2

Here is a reference implementation in JavaScript:

reward = (opponentMove, playerMove) => [[-1,0],[-3,-2]][opponentMove][playerMove]
playerFunc = (oppFunc, n, oppMoves=[], plaMoves=[], totalReward=0) => {
  if (n==0) { return [totalReward, plaMoves]; }
  oppNextMove = opponentFunc(oppMoves, plaMoves);
  finalOptimum = (plaNextMove) => 
    playerFunc(oppFunc, n-1, oppMoves+[oppNextMove], plaMoves+[plaNextMove], 
    totalReward+reward(oppNextMove,plaNextMove));
  silent = finalOptimum(0); betray = finalOptimum(1);
  return (silent[0]>betray[0]) ? silent : betray;
} 

//Testing
opponentFunc = (opponentMoves, playerMoves) => (playerMoves==[]) ? 0 : playerMoves[playerMoves.length-1]
console.log(playerFunc(opponentFunc, 5))

Questions

I think it might be better to just require outputting the maximum reward rather than the optimal set of moves, because it's easier to implement:

reward = (opponentMove, playerMove) => [[-1,0],[-3,-2]][opponentMove][playerMove]
playerReward = (oppFunc, n, oppMoves=[], plaMoves=[], oppNextMove = opponentFunc(oppMoves,plaMoves)) => (n==0) ? 0 : Math.max(reward(oppNextMove,0)+playerReward(oppFunc, n-1, oppMoves+[oppNextMove], plaMoves+[0]), reward(oppNextMove,1)+playerReward(oppFunc, n-1, oppMoves+[oppNextMove], plaMoves+[1])) 
\$\endgroup\$
1
  • \$\begingroup\$ this is a great idea. an example would be nice :-) \$\endgroup\$ Oct 8 at 20:30
0
\$\begingroup\$

TODO title

Given a word list, find all sets of five words of five letters each, such that the words of each set have 25 distinct letters in total.

This challenge was inspired by this video by Matt Parker.

Example

TODO

Rules

  • Standard I/O rules apply.
  • Words contain only lowercase (or alternatively, uppercase) alphabetic characters.
  • You can assume there are no empty words (i.e. words of length zero).
  • The input can contain words that cannot belong to any set that satisfies the property, such as words with less then five letters, words with more than five letters, and words with repeated letters.

Scoring

This challenge wants to be an experimental mix of and .

If your solution has:

  • a time complexity of \$\Omega(f(n))\$ (see Big Omega notation) where \$f: \mathbb N \to \mathbb N\$ is a function of the form $$f(n) = (\log_2 \log_2 n)^{k_{-2}} \cdot (\log_2 n)^{k_{-1}} \cdot n^{k_0} \cdot 2^{k_1} \cdot 2^{(2^{k_2})} \cdot \ldots $$ where \$n\$ the the total number of the letters of the words in the input;
  • a length of \$x\$ bytes (or whatever unit of measurement is commonly used in the language of your choice);

then the score is \$f(x + 4)\$. Lowest score wins!

Notes
  • obviously, infinitely many terms \$k_i\$ can be \$0\$;
  • terms with three or more \$\log\$ (e.g. \$\log_2 \log_2 \log_2 n\$) cannot be used in function \$f\$ because they could be used to arbitrarily lower the score, unless we introduce further complex scoring rules (and most probably they won't be used as a real lower bound).
Scoring example

If your solution has a length of \$37\$ bytes, and it has a time complexity of \$\Omega(n^5)\$, then it has a score of \$(37+4)^5\$.

\$\endgroup\$
4
  • \$\begingroup\$ can we assume that there will be at least one solution in the input? \$\endgroup\$ Oct 17 at 15:47
  • \$\begingroup\$ I didn't think about it. In which case this assumption can be useful? \$\endgroup\$
    – matteo_c
    Oct 17 at 22:01
  • 2
    \$\begingroup\$ I think that since the number of distinct five-letter words is constant, any algorithm taking a subset of them would be constant time. So, once you filter out words that not five letters long and de-duplicate, the complexity of the rest of the algorithm doesn't matter. Having the length "5" instead be a parameter could address this. \$\endgroup\$
    – xnor
    Oct 18 at 2:22
  • 1
    \$\begingroup\$ assuming at least one solution avoids the "no solutions" edge case, which (depending on algorithm) may require extra code to handle logic that the bulk of the code doesn't handle. Example: if i have a loop which doesn't stop until i've seen some N>0 eligible words, it would run into an infinite loop in the "no solutions" scenario. Considering you have to output all solutions, however, I can see how it might not make a huuge difference. It's up to you tbh :-) \$\endgroup\$ Oct 18 at 13:15
0
\$\begingroup\$

Minimum rotation to get the maximum value

\$\endgroup\$
2
  • \$\begingroup\$ Can you take the input as a list a b d c (or a c d b)? \$\endgroup\$ Oct 20 at 16:53
  • \$\begingroup\$ @CommandMaster Yes. \$\endgroup\$
    – oeuf
    Oct 21 at 1:07
0
\$\begingroup\$

Show a balanced binary tree

\$\endgroup\$
3
  • \$\begingroup\$ this is ascii-art tag. also, can we output via graphical-output instead? \$\endgroup\$
    – Steffan
    Oct 3 at 19:07
  • 1
    \$\begingroup\$ @Steffan I think that would be a meaningfully different challenge, so no. \$\endgroup\$ Oct 3 at 19:08
  • \$\begingroup\$ Suggested tag: open-ended-function \$\endgroup\$
    – DLosc
    Oct 10 at 21:11
0
\$\begingroup\$

Speed Checkers KOTH


For this King of the Hill challenge, your bot will play checkers against an opponent. However, you should be careful when making complex calculations, because both sides have a limited amount of time to play! Each side will start with 1,000,000 cycles [or 1 second, depending on what I use for the API] to spend during their turn, and if this runs out they will lose the game.



This is my attempt at making a KOTH challenge where your runtime matters.

Before I do the rest of the write-up, is the concept good? Is the amount of time given right? Should I use a simpler game? Should the API be in an assembly language, or in a Java runner?

\$\endgroup\$
2
  • \$\begingroup\$ I'm not certain but I thought checkers (draughts) was solved. It might not fit well in an answer, but once could just hardcode every possibility and play perfectly instantly. I think you need to pick a slightly more complicated game to make this work. \$\endgroup\$ Oct 27 at 17:57
  • \$\begingroup\$ Yes, it's solved, but you're not going to fit the entire move table in an SE answer. Solving it took I think years of calculation, so that's also off the table. \$\endgroup\$
    – RamenChef
    Oct 27 at 19:03
1
122 123
124
125 126
138

You must log in to answer this question.

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