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

2617 Answers 2617

1
\$\begingroup\$

Asked

\$\endgroup\$
  • 2
    \$\begingroup\$ Having posted and edited to just contain a link, you can also delete. \$\endgroup\$ – Peter Taylor Jun 13 '18 at 11:09
1
\$\begingroup\$

Add least char to match

Given a string, add at least chars to make the whole string match the given regexp. You can assume it's possible. If there are more than one solution, output a (not necessary uniform) random one.

Here regexp may contain:

|  or
() group
?  possibly not appear
*  may appear for any times. Maybe different in each match
0  
1

Samples

0100      (01)*         010101
0         (0|1)(0|1)    00; 01; 10 (any should possibly appear)
1010      ((0|1)(0|1))* 1010
101       ((0|1)(0|1))* 1010; 1011; 1001; 0101; 1101

\$\endgroup\$
  • \$\begingroup\$ Suggested question text for first para: "Given a string of 0s and 1s, and a regexp: add the minimum number of characters (0s and 1s) that makes the whole string match the given regexp. You can assume that this is possible. If there are multiple solutions of the same length, output any one of them." (This is meant to be a rewording of the same conditions, let me know if I've changed the task in some way with this wording.) \$\endgroup\$ – sundar - Reinstate Monica Jun 16 '18 at 12:10
  • \$\begingroup\$ @sundar Well I did only implied that the string can only contain 0 and 1, 2) I required random, though it may leads to lots of quite strange solutions(generate one that fit, generate another string of same length, if not match return the sure one) \$\endgroup\$ – l4m2 Jun 16 '18 at 12:13
  • \$\begingroup\$ " I did only implied that the string can only contain 0 and 1, 2" <- Are you saying that 2 is also allowed? I don't understand what you're saying here. " I required random, though it may leads to lots of quite strange solutions" <- Can you explain what you mean by random here, exactly? Your sample test case says "any should possibly appear", and that's what my proposed text says at the end ("not necessarily uniform random" seems to be a complicated way of saying the same thing). \$\endgroup\$ – sundar - Reinstate Monica Jun 16 '18 at 12:18
  • \$\begingroup\$ 2) meant it's the second point. "output any of them" seems it can be determistic as the result is valid @sundar \$\endgroup\$ – l4m2 Jun 16 '18 at 12:27
1
\$\begingroup\$

Draw the Recamán's Sequence

Recamán's sequence (A005132) is a mathematical sequence, defined as such:

A(0) = 0
A(n) = A(n-1) - n if A(n-1) - n > 0 and is new, else
A(n) = A(n-1) + n

A pretty LaTex version of the above (might be more readable):

pretty latex

The first few terms are 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11

(Description of the sequence borrowed from this older question).

Your task is to animate the drawing this sequence as a series of semi-circles:

Sequence construction

Where each entry above is a keyframe in the animation. Tween frames should draw the circle segment, and if necessary, scale the image down when the new locus would be out of frame.

After 600 terms of the sequence you should have something like this: Pattern (Image from this Numberphile video)

Your choice whether to draw horizontally, vertically, or diagonally, provided that the entire image fits within the image boundary. Line color can be any value, background can be any value (values must be distinct).

Winner

  • The program to generate the most terms of the sequence wins (before the program terminates, crashes, or otherwise corrupts the output--eg by exceeding file size limitations1).
  • Tie will go to the shorter program.

Rules

  • Output image size shall be no smaller than 2048x2048, compiled as a gif, apng, common video format (e.g. mp4), or as an HTML or Javascript canvas (in-place animation).
  • Segments should be drawn over 0.5 second intervals
  • Frame Rate should be no slower than 24 frames/second
  • (That is, each term of the sequence will take at least 12 frames to draw)
  • You need not embed the entire output in your answer, although some means of showing off the results of your work is expected (sped up version, choice stills, etc).

1 If your program will happily produce files in excess of 128 MB (the 64 bit NTFS file system will allow up to 16 TB files), post an altered version of your program that terminates after approximately 128 MB to avoid trashing people's hard drives. You may score based on the unaltered bytecount. Do please post a still image of the final frame your program could otherwise produce (within reason: you not required to generate the entire animation in order to determine true termination). You may use a modified / separate program to produce this still, as it is purely for aesthetic and curiosity purposes.

\$\endgroup\$
  • 2
    \$\begingroup\$ before the program terminates, crashes, or otherwise corrupts the output--eg by exceeding file size limitations ... Segments should be drawn over 0.5 second intervals. Frame Rate should be no slower than 24 frames/second These requirements are heavily dependent on the machine that one uses and therefore are difficult to measure objectively without a person testing every solution; i.e. you, the challenge poster, will have to run all submissions. \$\endgroup\$ – JungHwan Min Jun 19 '18 at 15:09
  • \$\begingroup\$ That's a fair point. \$\endgroup\$ – Draco18s Jun 19 '18 at 15:21
  • \$\begingroup\$ too many rules about time limits, output format, etc, imho \$\endgroup\$ – don bright Jul 7 '18 at 20:11
1
\$\begingroup\$

American Checkers AKA English Draughts

This is a king of the hill challenge for checkers/draughts enthusiasts.

Note: All code below is written in F#

Rules

For this game, I am using the rules from The American Checker Federation (Note: it tries to download a .doc file). The relevant rules are listed below.

Moving

Checkers move forward diagonally one square.
Kings move diagonally one square in any direction.

Capturing

Capturing is required in this variant.
Checkers jump forward diagonally two squares; they may only jump over an opponent's piece onto a blank square and continue jumping until there are no more pieces to jump, or until they reach the king row.

King jumps follow the same pattern as checkers jumps, but do not have the restriction on moving forward.

Winning

The game is won when one player has no more pieces or cannot make any more moves.

Draws

A draw is declared when the same position is reached three times or when neither player moves an unkinged checker for 40 moves and there are no captures in those forty moves.

Play

Each program will take a list of the game history in the form of a PdnTurn list (Read about PDN notation here):

type PieceType = Checker | King
type PdnMove = { Move :int list; ResultingFen :string; DisplayString :string; PieceTypeMoved :PieceType Option }
type PdnTurn = { MoveNumber :int; BlackMove :PdnMove; WhiteMove :PdnMove Option }

It will return the data in the form of a list of ints, where each int represents a square on the board. That is, if you have a piece on square 1 and intend to jump to square 10 over a piece on square 6, your program will return [1; 10] (notation as an F# list). If any player returns an invalid move, they forfeit the game.

Scoring

Each player will play three games against each opponent; each win will be scored as 1, each loss as 0, and each draw as 1/2. The loser of the match will be disqualified. At the end of the tournament, the player(s) with the highest score win.

The Tournament (incomplete):

I set up a website at checkerstreasury.azurewebsites.net. Communication from the server to the player is done with SignalR preferring websockets (you can probably just use websockets without SignalR, but I don't know how). Communication from the player to the server is done with POST requests. I am at work now, but I will post the API and finalize this later.

This challenge feels incomplete; am I missing something?

Question: I have my own AI implemented alongside my controller. I intend on submitting this as a base submission, but will not award it the win even if it is the king of the hill. Should I include it in the question, or as an answer? If an answer, should I post it with the question, or wait a while?

\$\endgroup\$
  • 1
    \$\begingroup\$ In the interests of the challenge being self-contained I'd suggest providing a summary of the rules that would be sufficient for people to complete it without relying on external resources. \$\endgroup\$ – Shaggy Feb 24 '18 at 21:22
  • \$\begingroup\$ @Shaggy Relevant rules added. \$\endgroup\$ – Hosch250 Feb 24 '18 at 23:04
  • \$\begingroup\$ I think Mego has an identical koth? Let me check... \$\endgroup\$ – user202729 Feb 25 '18 at 3:42
  • \$\begingroup\$ Here. \$\endgroup\$ – user202729 Feb 25 '18 at 3:43
  • \$\begingroup\$ Thanks, @user202729. \$\endgroup\$ – Hosch250 Feb 25 '18 at 4:17
  • \$\begingroup\$ Do you intend to post this at some point? I might be interested to write a challenge and a language-agnostic controller (using STDIO and/or argv for I/O), but apparently you and Mego have both created a sandbox post on the same topic. \$\endgroup\$ – PurkkaKoodari May 25 '18 at 23:53
  • \$\begingroup\$ I actually wrote a website for my checkers game over the last few weeks. I'm just working out a few more bugs before it is ready. It has an API for bots to tap in to, and all. Check it out at checkerstreasury.azurewebsites.net (note that steady activity playing the computer by a few users gets it rate-limited as I'm using the free option). \$\endgroup\$ – Hosch250 May 26 '18 at 1:53
  • \$\begingroup\$ Website "done". I'll finalize this soon! \$\endgroup\$ – Hosch250 Aug 4 '18 at 22:36
1
\$\begingroup\$

Execute a Subpar Shuffle™

Inspired by the Execute a Superb Shuffle™ challenge, and a shuffling method I used as a young child before I realised how bad (and time consuming) it is.

In a Subpar Shuffle, you take the deck of cards, and perform the following actions:

  1. Take the top card of the deck and deal it out into a pile.
  2. Take the next card of the deck and place it underneath the deck.
  3. Repeat steps 1 & 2 until you've dealt out the whole deck.

If your deck is represented as a list, then it looks something like this:

  1. Set up an empty list to hold the shuffled list.
  2. Put the first item of the old list at the start of the new list.
  3. Put the first item of the old list at the end of the old list.
  4. Repeat 2 & 3 until the old list is empty, then return the new list.

So, for example, the input list [1, 2, 3, 4] would result in the following:

Old list     | New list
[1, 2, 3, 4] | []
[2, 3, 4]    | [1]          Put the 1 at the start of the new list
[3, 4, 2]    | [1]          Put the 2 at the end of the old list
[4, 2]       | [3, 1]       Put the 3 at the start of the new list
[2, 4]       | [3, 1]       Put the 4 at the end of the old list
[4]          | [2, 3, 1]    Put the 2 at the start of the new list
[4]          | [2, 3, 1]    Put the 4 at the end of the old list
[]           | [4, 2, 3, 1] Put the 4 at the start of the new list

So the final Subpar Shuffled list is [4, 2, 3, 1].

Here are a few more test results for Subpar Shuffling of various lists:

Input                     | Output
[]                        | []
["Ace of Spades"]         | ["Ace of Spades"]
["A","c","e","o","f","S"] | ["o","S","c","f","e","A"]
[1,2,3,4,5,6,7,8,9,0]     | [4,8,0,6,2,9,7,5,3,1]
\$\endgroup\$
  • \$\begingroup\$ Will we be guaranteed that each element in the input list is unique? \$\endgroup\$ – Shaggy Jun 19 '18 at 21:24
  • \$\begingroup\$ That's a fair question. I think that for the purpose of this challenge, I would say yes (although I don't see that it makes much difference). \$\endgroup\$ – ConMan Jun 19 '18 at 23:21
1
\$\begingroup\$

Binary Positional Average

Introduction

(This challenge is from work today) This challenge seems relevant for actual use in the real world, it's a (as far as i know) not yet dealt with kind of integer sequences.

Challenge

  • Inputs: A Integer between 1 and 64 representing the amount of bits to iterate through
  • Output: An Array or a delimiter separated sequence of arrays or sequences of 0s and 1s

The algorithm has to take the input and generate all binary sequences up to the given number ordered by the position of the average 1 bit in the binary representation of the current number. The direction of the sorting is irrelevant. 0 can be ignored.

The solution must terminate, otherwise this is code golf, tiebreaker is performance in program steps.

Example Input and Output

Input:

4

Has (among others) the following possible outputs:

0001,0011,0101,0010,0111,1011,0110,1111,0000,1001,1101,1110,1010,0100,1100,1000

Or:

0001,0011,0111,0010,0101,1011,0110,1111,1001,1101,1010,1110,0100,1100,1000

Example Implementation

(Javascript - modified sketch from work)

function binaryPositionalAverage(size) {

    let srMap = [];

    for (let i = 2**size -1; i > 0; i--) {

        let inp = (i).toString(2);
        let out = "";
        // pad with 0s
        for (let i = 0; i < (size - inp.length); i++) {
            out += "0";
        }
        out += inp;
        out = out.split("").map(s => parseInt(s));
        // out format: [1,1,1,1];

        let rating = 0;
        let divisor = 0; // we ignore 0 by loop condition
        for (let k = 0; k < out.length; k++) {
            if (out[k]) {
                rating += k+1;
                divisor++;
            }
        }
        rating /= divisor;

        srMap.push({
            rating: rating,
            binary: out,
        });
    }
    return srMap.sort((a, b) => a.rating - b.rating).map(e => e.binary);
}
\$\endgroup\$
  • \$\begingroup\$ I find the description rather confusing because of the way it switches between talking about numbers and binary sequences without warning, but I'm pretty sure that the second example output is wrong. Ordering from 0001 to 1000 the order must begin 0001,0011. Then 0010,0101,0111 in any order; then 1011; then 0110,1001,1111 in any order, then 1101; then 0100,1010,1110 in any order; and finally 1100,1000. Plus 0000 somewhere if desired. \$\endgroup\$ – Peter Taylor Jun 19 '18 at 8:46
  • \$\begingroup\$ @PeterTaylor you are right sir, the second output is wrong I'll go ahead and rewrite the challenge later this afternoon to talk about binary representation of numbers, and provide a reference implementation \$\endgroup\$ – S. Janssen Jun 19 '18 at 10:42
  • \$\begingroup\$ Pretty sure this is a dupe but can't quite come up with the right search terms to find it. \$\endgroup\$ – Shaggy Jun 19 '18 at 21:18
  • \$\begingroup\$ @Shaggy I'm not sure, weather i should react to this comment. If the challenge is a dupe, please provide some kind of proof, and I'll delete it; On another note: How would you improve it? \$\endgroup\$ – S. Janssen Jun 19 '18 at 22:35
  • \$\begingroup\$ Does 0 can be ignored mean that 0 can be sorted anywhere in the sequence? Or does it mean that it can be omitted, but if it is included it should be sorted as in the example? \$\endgroup\$ – Emigna Jun 21 '18 at 8:54
  • \$\begingroup\$ What do you mean by The solution must terminate. Only that it can't get stuck in an infinite loop, or do it need to finish for n = 64 within a specific amount of time on a specific set of hardware? I presume it is the former as generating and sorting 18446744073709551616 strings will take a while. \$\endgroup\$ – Emigna Jun 21 '18 at 9:04
1
\$\begingroup\$

A fast-growing evaluator

Introduction

The fast-growing hierarchy is a hierarchy of, well, fast-growing functions, with a one-to-one correspondence to ordinals. If you did some challenges, you may have worked with them, since it's a systematic means of defining functions with extremely fast growth rates.

Here, you are defining as many of them as you can. Of course, because of obvious problems with enumerating them sequentially, the challenge is to yield any particular one given the ordinal, up to as far an upper limit as possible.

The fast-growing hierarchy

If you are lost on some of the jargon here, I recommend a read about ordinals: https://en.wikipedia.org/wiki/Ordinal_number

The fast growing hierarchy is defined for each ordinal in a recursive manner as follows:

  • The lowest and slowest function, corresponding to 0, is f0(n) = n+1.

    • f0(3) = 3+1 = 4
  • For succeeding ordinals and functions in the hierarchy, fa+1(n) = fan(n).

    • f1(2) = f02(2) = f0(f0(2)) = f0(3) = 4
  • For functions in the hierarchy corresponding to limit ordinals, first determine a fundamental sequence that approaches the ordinal in question. Then, fa(n) = fa[n](n), where a[n] is the nth ordinal in the fundamental sequence.

    • The fundamental sequence of ω is {0, 1, 2, 3...}, indexing from zero. So fω(2) = f2(2) = f1(f1(2)) = f1(4) = 8

As can be seen, for infinite-ordinal entries of the fast-growing hierarchy, the value of the function is dependent on the choice of fundamental sequences. Most ordinal notations specify fundamental sequences with the ordinals that they define notations for.

Here are some typical choices of ordinal notations and fundamental sequences, arranged in increasing ordinal-notating capability:

The challenge

Within 1024 bytes, write a program that takes the string representation of an ordinal A in some ordinal interval starting at 0, and a number B of arbitrary size, and prints the fast-growing function corresponding to A, applied to B.

  • Choices of domain of representation, ordinal domain, ordinal notation, and ordinal fundamental sequences must be specified. The choice of fundamental sequences must actually approach the ordinals they define fundamental sequences to, such that logically, the ωth ordinal of that sequence would be the ordinal of that fundamental sequence.
  • The program must provably halt for any input, given sufficient resources, even for invalid inputs or inputs corresponding to ordinals beyond the program's capability. In particular, raw eval() of the input is forbidden, and entries are disqualified if they permit arbitrary code execution.
  • For all given ordinals with the program's capability, the program must print the value as described above for all numbers, deterministically, given enough resources.
  • Standard restrictions on running time and resource usage of programs are relaxed.
  • Competing entries must be able to handle at least A=0.

Scoring

Take C to be the first ordinal for which the program fails to satisfy the requirements above, and D to be the difference between your program byte length and 1024, the maximum byte length of submissions. Then your score is C+D.

Sample scores:

  • Alice, in 200 bytes, writes a program for which A can be any natural number. Her score is ω+824.
  • Bob, in 220 bytes, writes a program for which A can be ω or any natural number. His score is (ω+1)+804 = ω+805.
  • Carol, in 400 bytes, writes a program for which A can be any ordinal purely in Cantor normal form. Her score is ε0+624.
  • Dave, in 700 bytes, writes a program for which A can be a natural number or any epsilon number. His score is ω+324.
  • Eve, in 300 bytes, writes a program which segfaults if A is represented by a decimal string longer than 65536 bytes. Her score is 1065536+724.
\$\endgroup\$
  • \$\begingroup\$ We already have mathjax... \$\endgroup\$ – user202729 Jun 23 '18 at 14:28
  • \$\begingroup\$ @user202729 The challenge is around making a program that can do as asked, to as far a scale as its resources can handle. Of course no computer can have truly infinite resources, but it's the effort to get there that I'm aiming for. The allowance for people to specify their own input, up to reasonable bounds, is to let people specify the infinite ordinals in finite space, say by using the greek letter omega to represent its corresponding ordinal. \$\endgroup\$ – eaglgenes101 Jun 23 '18 at 15:24
  • \$\begingroup\$ However...... you can make your program work for all computable ordinal by make (the notation of an ordinal) = (the function which when given \$n\$ returns the \$n^{th}\$ element in one of its fundamental sequence if it's a limit ordinal, else something contains its pred). \$\endgroup\$ – user202729 Jun 23 '18 at 15:36
  • \$\begingroup\$ The key words are "given enough resources". A program that uses large arrays may choke on a microcontroller but function just fine on a desktop and a supercomputer, and can be designed so it functions essentially the same in the latter two cases, and naturally scales for bigger requirements given more resources. No one will have enough resources to create a computer that can work with some of the hugest defineable numbers, but that doesn't stop people from creating challenges where outputting such huge numbers is the goal of the challenge. \$\endgroup\$ – eaglgenes101 Jun 23 '18 at 15:38
1
\$\begingroup\$

Assign tasks to processors anything better to put here?

Given a list of processor speeds \$S\$, where each element denotes how many ticks the processor at its index takes to complete a task, and a number of tasks \$N\$, replace every element in \$S\$ with the number of tasks the processor at its index should perform. The order of completion doesn't matter, and the tasks aren't enumerated anyway. The processors you pick don't matter either. The only thing that matters is that the ticks needed to complete all the tasks are the least possible. If there are multiple solutions, choose one with the lowest sum of the ticks each processor spends working (less man-hours means happier workers). This is a simple version of such a challenge, so you can assume that every task takes the same amount of time to be completed. You can assume that \$S\$ only consists of positive integers and that its length is at least \$1\$, and \$N\$ is a non-negative integer. What a blob of text...

Examples (test cases)

\$S=[4,1,3,1,2,2,1,1]\\N=13\\\text{Example output: }[0,3,0,3,1,0,3,3]\$

\$S=[8]\\N=28\\\text{Example output: }[28]\$

\$S=[1,1,1,1,1,1,1,1,2]\\N=5\\\text{Example output: }[1,1,1,1,1,0,0,0,0]\$

\$S=[1,28]\\N=28\\\text{Example output: }[28,0]\$
Note that \$[27,1]\$ is an invalid output, since \$1\times27+28\times1>1\times28\$.

\$\endgroup\$
  • \$\begingroup\$ Can I output work time of each processor? (speed × number of work) \$\endgroup\$ – user202729 Jul 6 '18 at 10:18
  • \$\begingroup\$ @Emigna [0, 2, 0, 3, 0] is also invalid. There's [0, 2, 0, 2, 1] which completes all the tasks in 2 ticks, while yours does so only after 3 ticks. The lowest sum is only a tiebreaker, and, if there are still ties, you can choose any possible output. I guess that's not clear enough. \$\endgroup\$ – Erik the Outgolfer Jul 6 '18 at 10:58
  • \$\begingroup\$ @user202729 Sorry, no. It does make some sense, but I don't want a multiple-output challenge. \$\endgroup\$ – Erik the Outgolfer Jul 6 '18 at 11:01
  • \$\begingroup\$ @EriktheOutgolfer: Ah, right. \$\endgroup\$ – Emigna Jul 6 '18 at 11:12
1
\$\begingroup\$

Integers in increasing order of width when printed in Helvetica

XKCD 2016

According to Explain XKCD, Helvetica kerns adjacent 1s together slightly. This means that the sequence of integers in increasing order of width is (0, ) 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 12 ... 99, 111, 110, 112 ... 119, 211, 311, 411, 511, 611, 711, 811, 911, 100 ... 109, 120 ... 210, etc.

For the purposes of this question you can assume that repunits will always print wider than numbers with fewer digits. Note that the adjacent pairs may overlap e.g. 11011 has the same width as 11100.

Given an integer n, either return the nth integer in the sequence (you may but do not need to support the 0th integer as 0) or the first n integers (starting at either 0 or 1). Alternatively, print the sequence indefinitely or return a generator or equivalent lazy list.

This is , so the shortest program or function that breaks no standard loopholes wins!

(Should I include negative integers? They could be assumed to be longer than all positive integers with the same number of digits, but shorted than those with more digits.)

\$\endgroup\$
  • 2
    \$\begingroup\$ From explain xkcd: "This sequence is not uniquely defined" ...? Also which is longer, 30 1's or 29 2's? \$\endgroup\$ – user202729 Jul 8 '18 at 3:15
  • \$\begingroup\$ @user202729 "For the purposes of this question you can assume that repunits will always print wider than numbers with fewer digits." \$\endgroup\$ – Neil Jul 8 '18 at 8:45
  • \$\begingroup\$ Still, what about 1111110 and 222220? Both are not repdigits. \$\endgroup\$ – user202729 Jul 8 '18 at 10:59
  • \$\begingroup\$ @user202729 Well, you already know you can assume 111111 is wider than 22222... \$\endgroup\$ – Neil Jul 8 '18 at 16:43
  • \$\begingroup\$ So what? 1 is not shorter than 2, but 11 is shorter than 22. Exactly what are we supposed to do? \$\endgroup\$ – user202729 Jul 8 '18 at 16:44
  • \$\begingroup\$ @user202729 Sort by length and by number of pairs of adjacent 1s. \$\endgroup\$ – Neil Jul 8 '18 at 16:51
  • \$\begingroup\$ I think you should state explicitly that numbers should be first sorted by number of digits then by number of consecutive 1s (if I understood correctly and that is true). \$\endgroup\$ – dylnan Jul 8 '18 at 19:05
  • 1
    \$\begingroup\$ my suggestions. 1. explain what a 'repunit' is. 2. explain what 'kerning' is, actually 3. give a basic explanation of how typesetting works in a computer and how something like this can be measured. 3. specify non-negative integers. 4. is it true that all numbers in helvetica have same width except 1? \$\endgroup\$ – don bright Jul 11 '18 at 1:10
1
\$\begingroup\$

Play a Game of Balls Bounce

The game Balls Bounce consists of the following:

  • a number of blocks, each containing a \$durability\$ number \$\geq 1\$
  • a field of dimension \$h \times w\$, partially filled with blocks (field is \$9\times 7\$ in the example)
  • a number of \$balls\$, positioned in one location at the bottom of the field

Rules of the game:

  • The player chooses a direction in which all the balls will be shot sequentially.
  • Each time a ball hits a block, that block's \$durability\$ decreases by \$1\$.
  • A block that has its \$durability\$ decreased below \$1\$ is removed from the field.
  • Balls that hit a block are deflected and continue to fly. Note that one ball may be deflected multiple times and hit the same block more than once.
  • Balls do not interact with each other directly. They may be in the same place at the same time.
  • If a ball touches the top, left, or right side of the field, it gets deflected in a similar manner.
  • If a ball touches the bottom of the field, it gets stuck there and won't continue to fly this round.
  • A round ends once there are no more balls flying around.
  • After a round ends, all blocks on the field move one row downwards, and new blocks spawn in the top row.
  • The player loses if any block goes past the bottom line.

Note that \$balls\$ might be higher than \$durability\$ of the first block that is hit. In that case, the player now has to keep to paths in mind: the first, a \$durability\$ amount of balls, is deflected by the block, while the second, a \$durability - balls\$ amount passes through the position where the now destroyed block once was.

In the mobile game, the player can choose some angle for the shot. Because I want to make this challenge not bigger than it already is, there is only three possible angles to choose from: 45° to the left, denoted by \$L\$, straight upwards, denoted by \$U\$, and 45° to the right, denoted by \$R\$. Also, the first ball to touch the bottom line marks the position from which the nex round's shot will be taken. For simplicity's sake, all shots will be taken from the middle of the baseline. If a grid has even \$w\$, left of the middle is chosen. If an ambiguity would be created by two balls interacting with the same block at once, the ball that was shot first interacts first.

Input

  • The Field with Blocks

    You may take this as a \$h \times w\$ 2D array of integers or strings. Each value represents the \$durability\$ of the block at that position. You may choose something other than \$0\$ to represent an empty space.
  • The Amount of Balls

    Quite self-explanatory. Integer (or any convenient format).
  • The Direction

    One of \$\{L, U, R\}\$. You may choose the three strings "L", "U" ,"R" to represent this, but any three distinct and consistent values will suffice.

Output

  • Is the game over?

    Output a truthy value if the game is lost after this round, and a falsy one if the game can go on. Any two distinct and consitent values will suffice.

This is , so shortest code in bytes for each language wins.


Example:

Input:

Field

[0][0][0][0][0]
[0][9][0][0][0]
[0][0][1][0][1]
[0][0][0][2][0]

Balls 3

Direction "R"

Output:

False

Step-by-step:

-----------------------
          (1)
-----------------------
#######################   #  border of field
#+---+---+---+---+---+#   
#|   |   |   |   |   |#   +  corner of block/empty cell
#+---+---+---+---+---+#   -  horizontal border of block/empty cell
#|   | 9 |   |   |   |#   |  vertical border of block/empty cell
#+---+---+---+---+---+#   
#|   |   | 1 |   | 1 |#
#+---+---+---+---+---+#
#|   |   |   | 2 |   |#   2  durability
#+---+---+---+---+---+#
###########o###########   o  ball
           3              3  number of balls remaining to be shot

-----------------------
          (2)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   | 1 |   | 1 |#
#+---+---+---+---+---+#
#|   |   |   o 1 |   |#      the first block is hit, durability decreased to 1
#+---+---+--/+---+---+#   /  "tail" to show the direction of the ball
###########o###########
           2

-----------------------
          (3)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   | 0 |   | 1 |#      second block decreased to 0, ball that hit it is deflected
#+---+---+-o-+---+---+#
#|   |   |   o 0 |   |#      same for the first block
#+---+---+--/+---+---+#
###########o###########
           1

-----------------------
          (3)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   |   |   | 1 |#       
#+---+---+-o-+---+---+#
#|   |   o   o   |   |# 
#+---+---+---+---+---+#
###########-###########
           0

-----------------------
          (4)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 9 |   |   |   |#
#+---+---+---+---+---+#
#|   |   o   |   | 1 |#       
#+---+---+---+-o-+---+#
#|   |   |   |   |   |# 
#+---+-o-+---+---+---+#      first ball hit the bottom line...
###########-###########
           0

-----------------------
          (5)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   | 8 |   |   |   |#
#+---+-o-+---+---+---+#
#|   |   |   |   o 0 |#       
#+---+---+---+---+---+#
#|   |   |   |   |   |# 
#+---+---+---+---+---+#      ... and is removed subsequently
###########-###########
           0

-----------------------
       (6 to 19)
-----------------------
#######################
#+---+-*-+---+---+---+#      *  path of the right ball
#|   *   *   |   |   |#
#+-*-+---+-*-+---+---+#
#*   | 8 |   *   |   |#
#+-*-+---+---+-o-+---+#
#|   o   |   |   |   |#      °  path of the left ball
#+-°-+-*-+---+---+---+#
#°   |   *   |   |   |# 
#+-°-+---+-*-+---+---+#
###########-###########
           0

-----------------------
          (20)
-----------------------
#######################
#+---+---+---+---+---+#
#|   |   |   |   |   |#
#+---+---+---+---+---+#
#|   |   |   |   |   |#      all balls are gone, blocks are shifted down
#+---+-V-+---+---+---+#      no block reaches the bottom line, so no game over
#|   | 8 |   |   |   |#       
#+---+---+---+---+---+#      Return false
#|   |   |   |   |   |# 
#+---+---+---+---+---+#      
###########-###########
           0

The step-by-step diagram is just for illustrative purposes. You are not required to print any of the above.


Sandbox Questions

As this is my first challenge on here, I need some guidance. What examples should be added to clarify the task? What corner cases hould I take into consideration? And most importantly, is it clear what my challenge will be?

\$\endgroup\$
  • \$\begingroup\$ What happens if a ball hits a corner of a block rather than a side? \$\endgroup\$ – AdmBorkBork Jul 11 '18 at 13:16
  • \$\begingroup\$ @AdmBorkBork This is not possible, since the ball always starts in the middle of the bottom of the bottom line's center cell, and move diagonally or vertically. Only the middles of a cell's sides can be hit this way. Should I add an illustration to clarify this? In the original game, if a ball hit a block exactly on the corner, it would be reflected in the opposite direction it came from, taking its path back. I can add this rule, but it should never occur with angles constrained to {45, 90, 135} degrees. \$\endgroup\$ – Orphevs Jul 11 '18 at 14:00
  • \$\begingroup\$ Then maybe just a sentence saying "The ball is guaranteed to never hit a block on the corner." or something, just to completely rule it out. I get what you're saying with the angles, and that makes sense now that I read it again, but it'd be good to have definitive clarification. Nice challenge, otherwise! \$\endgroup\$ – AdmBorkBork Jul 11 '18 at 16:11
  • \$\begingroup\$ @AdmBorkBork Ill think about a way to rephrase my rules so this becomes more clear. Will add your suggestion later when I'm home :) Thank you. \$\endgroup\$ – Orphevs Jul 12 '18 at 1:01
  • \$\begingroup\$ @AdmBorkBork I couldn't think of any corner cases that might come up. Do you have ideas for that? \$\endgroup\$ – Orphevs Jul 12 '18 at 1:05
  • \$\begingroup\$ Corner cases would be things like: A block that can't be reached directly but requires a ricochet to hit, a block by itself on the field, a block that if not hit will result in a game over (that's covered in your example), a field with two blocks that will cause a game over and the balls can only hit one, etc. I would recommend guaranteeing that an empty field will not exist. \$\endgroup\$ – AdmBorkBork Jul 12 '18 at 14:45
1
\$\begingroup\$

Drawing a convex polyiamond

A subtask of Drawing convex polyiamonds. I consider the drawing part hard enough on itself.

A polyiamond is a polygon made from equilateral triangles. For example: (example in ASCII art)

  *
 / \
*---*

Or:

  *---*
 / \ / \
*---*---*
 \ /
  *

(with lines drawn between the triangles for clarity)

While the first polyiamond is convex, the second one is not.


Consider a convex polyiamond. All of its internal angles must be less than 180°. Also, the internal angle of a triangle is 60°, so each vertex must be 60° or 120°.

Assume a polyiamond has all 120° angles. It must have 6 edges.

Given the length of those 6 edges, it's either possible to reconstruct the polyiamond uniquely, or there are no such polyiamond. For example:

(1,1,1,1,1,1) ->

  *---*
 / \ / \
*---*---*
 \ / \ /
  *---*

(1,2,1,2,1,2) ->

  *---*---*
 / \ / \ / \
*---*---*---*
 \ / \ / \ /
  *---*---*
   \ / \ /
    *---*

Now consider a 60° internal angle. It can be assumed to be two consecutive 120° angle with the intermediate edge have length 0. For example:

(0,1,0,1,0,1) ->

  *
 / \
*---*

Your program should take a list of 6 non-negative integers (in any convenient format such as: tuples, string of comma-separated integers, \$2^a 3^b 5^c 7^d 11^e 13^f\$ (for Fractran?)) which represents a valid convex polyiamond, and output the polyiamond as ASCII art.

It's guaranteed that:

  • No numbers in the list will exceed 12.
  • It's guaranteed that there is at least 1 cell in the output. (so (0,0,1,0,0,1) is not a valid input) Equivalently, no two consecutive 0's can appear in the input list.
\$\endgroup\$
  • 1
    \$\begingroup\$ Please upvote this comment if you think the challenge is ready to be posted on main. \$\endgroup\$ – user202729 Jul 17 '18 at 9:07
  • 1
    \$\begingroup\$ Please upvote the post if you think the challenge is interesting, and downvote the post if you think the challenge is not interesting. If the post has enough downvotes I will not post it. \$\endgroup\$ – user202729 Jul 17 '18 at 9:07
  • \$\begingroup\$ Please upvote this comment (or just leave a comment) if you think the challenge has something that needs to be fixed. \$\endgroup\$ – user202729 Jul 17 '18 at 9:07
  • \$\begingroup\$ I have to leave the comments above because it may be unclear how voting in the sandbox works. \$\endgroup\$ – user202729 Jul 17 '18 at 9:09
1
\$\begingroup\$

Given a list of variable names and a list of monomials, output a string representation of the name of the polynomial. The monomials should be represented as pairs [coefficient, vector of exponents] where the vector of exponents has the same length as the list of variable names.

Combine like terms, omit terms that have coefficient zero, and output the resulting polynomial.

If the list of variables is ["x", "y", "z"] then [c, [i,j,k]] represents the monomial c*x^iy^jz^k, so for example [2, [1,2,3]] should be printed as 2xy^2z^3 and [-1, [0,1,2]] should be printed as -yz^2.

A worked example:

Input ["x","y"], [[4,[2,1]], [1,[0,0]], [-1,[1,1]],[-2,[2,1]]]: The monomial [2,1] which corresponds to x^2y is repeated twice, [4,[2,1]] with coefficient 4 and [-2,[2,1]] with coefficient -2 so we add those two coefficients together to get 2x^2y.

[1,[0,0]] corresponds to 1x^0y^0 which should be displayed as 1 and [-1,[1,1]] corresponds to -1x^1y^1 which should be displayed as -xy. The polynomial is the sum of these three, so all together the output should be 2x^2y - xy + 1 or some reordering of these terms.

Requirements:

  • Operators can be surrounded in spaces
  • Like terms should be combined.
  • If the exponent is 1 it should be omitted: x, not x^1. If the exponent is zero, the variable should be omitted entirely: y not x^0y and 1 not x^0y^0.
  • Empty polynomials should be represented as 0.
  • Terms with coefficient zero should be dropped. A coefficient of 1 should be omitted unless all exponents are zero.
  • A negative coefficient should be written with a minus sign. If the first monomial has a positive coefficient, it should not be preceded by a +.
  • Terms can be output in any order

Test Cases

Input: ["x"], [] ==> "0"
Input: [], [[3,[]], [-7,[]]] ==> "- 4"
Input: ["x"], [[0,[5]]] ==> "0"
Input: ["x"], [[1,[5]]] ==> "x^5"
Input: ["x"], [[-1,[5]]] ==> "- x^5"
Input: ["x"], [[1,[5]], [1,[5]]] ==> "2x^5"
Input: ["x"], [[1,[5]], [-1,[5]]] ==> "0"
Input: ["x"], [[1,[2]], [2,[1]], [3,[0]]] ==> "3 + 2x + x^2"
Input: ["x"], [[3,[0]], [2,[1]], [1,[2]]] ==> "3 + 2x + x^2"
Input: ["x", "y", "z"], [[1,[0,0,1]], [1,[1,0,0]], [-1,[0,1,0]]] ==> "x - y + z"
Input: ["x_1", "x_2"], [[1,[1,1]],[1,[2,2]]] ==> "x_1x_2 + x_1^{2}x_2^{2}"
Input: ["x", "y"], [[2,[2,2]], [3,[2,1]], [4,[2,0]], [1,[0,0]], [-1,[1,0]],[-2,[2,0]]] ==> 
        "1 - x + 2x^2 + 3x^2y + 2x^2y^2"
\$\endgroup\$
1
\$\begingroup\$

Syllabification and classification (Venpa)

Introduction

Venpa is a form of classical Tamil poetry, based upon certain rules of metric prosody. The complete rules form a context-free grammar, the task here is to test for a tiny subset of those rules.

Letters

  • Vowels: a, A, i, I, u, U, e, E, y, Y, o, O, W
    • small case represents "short" vowels, CAPS represent "long" vowels
    • y represents the y sound in "my".
    • W represents the "ou" sound in "mouse", and always comes in capital (long) form.
  • Consonant: everything else
    • the consonants can be in small case or capitals, whichever is convenient.

Word Segmenting

Words in the input are seen as composed of segments (which roughly correspond to the usual notion of a syllable). A segment divide occurs where:

  • two or more consonants occur together, tr, rpp, etc.
  • a long (capital) vowel occurs in the word, pO, W, mY etc.
  • two vowels have occurred since the last segment's end (or the word's beginning).

sanjIvi has segments san, jI, vi.
Yvar has Y,var.
vigadakavi has viga,daka,vi.
vAnily has vA,nily.
padAgytAngiha has padA, gytAn, giha
radagajaturagapadAdi has rada, gaja, tura, gapa, dA, di

(Consonants at the end of segments make no difference after segmentation and can be ignored - gytAn=gytA, var=va.)

As you can see, the segments are of two types:

  1. those with a single vowel, san, Y, vA, called a straight (S) segment
  2. those with two vowels, viga, nily, padA called a sequence (Q) segment

So the segment patterns of the above words are:

  sanjIvi              =              san + jI + vi          = SSS
  Yvar                 =                 Y + var             = SS
  vigadakavi           =            viga + daka + vi         = QQS
  vAnily               =                vA + nily            = SQ
  padAgytAngiha        =           padA + gytAn + giha       = QQQ
  radagajaturagapadAdi = rada + gaja + tura + gapa + dA + di = QQQQSS

Permitted patterns

The rules for words allowed in a Venpa are:

  1. a word should have one to three segments
  2. a one or two segment word can have any pattern (S, Q, SQ, SS, QS, QQ)
  3. a three segment word must end in a straight (S) segment

So out of the above, SSS, SS, QQS, and SQ are allowed, QQQ and QQQQSS are not.

Task

Given an input word in the above letters, output its segment pattern if it's an allowed word, or a false-y value if it's not an allowed word.

Input

  • Will be a single word composed of the characters mentioned under the Letters heading above
    • (Small case w will not be present anywhere in the text (neither as a vowel nor as a consonant))

Output

  • The segment pattern of the input word, if it's an allowed word
    • can use any two distinct unambiguous characters to represent S segments and Q segments
  • A false-y value in your language if it's not an allowed word
  • Output is undefined for invalid input (i.e. has characters other than those specified)

Test cases

vigadakavi 
=> QQS
Yvar 
=> SS
padAgytAngiha
=> falsey (QQQ not allowed)
vAnily
=> SQ
katradanA
=> SQS
radagajaturagapadAdi 
=> falsey (more than 3 segments)
TuppArkkuT
=> SSS
mazai
=> Q
\$\endgroup\$
  • 1
    \$\begingroup\$ fascinating. im probably very unusual, but i would like it even better if it was actual poetry instead of 'p' everywhere, maybe even in tamil script (although that would probably disqualify some languages) \$\endgroup\$ – don bright Jul 7 '18 at 2:37
  • 1
    \$\begingroup\$ Yeah, I intended to just remove some extraneous complexity, but somehow having input in this form makes it slightly less interesting even to me (and I'm not sure it removes a meaningful level of complexity anyway, relative to the rest of the task). I'll change it to use the actual consonants if anyone else here also feels this way. (The last two test case inputs are from actual poetry by the way, just with the consonants replaced.) \$\endgroup\$ – sundar - Reinstate Monica Jul 7 '18 at 18:54
  • 1
    \$\begingroup\$ Using Tamil script would also be great, but my concern with that is mainly that it might make testing and debugging much harder for people who can't read the script. I can mitigate some of that by providing exhaustive test cases, but I'm not sure it's worth it. \$\endgroup\$ – sundar - Reinstate Monica Jul 7 '18 at 18:58
  • \$\begingroup\$ yeah i think i might be a little unusual in my tastes, i still like the puzzle... \$\endgroup\$ – don bright Jul 7 '18 at 20:08
  • 1
    \$\begingroup\$ @donbright I've updated the post to use different consonants (corresponding to actual words). I like this version a lot better, but let's see how it's received. \$\endgroup\$ – sundar - Reinstate Monica Jul 20 '18 at 14:18
  • \$\begingroup\$ I wrote a program that solves the examples you gave. my first pass was 60 lines of Rust code. i think it is a really good puzzle, great balance between an interesting puzzle and many ways to possibly reduce code size. very interesting. \$\endgroup\$ – don bright Dec 29 '18 at 14:10
  • \$\begingroup\$ i would like some more examples though. feel like my program might be wrong on some inputs. \$\endgroup\$ – don bright Dec 29 '18 at 14:11
1
\$\begingroup\$

Lord Vetinari's Clock

Someone very clever — certainly someone much cleverer than whoever had trained that imp — must have made the clock for the Patrician’s waiting room. It went tick-tock like any other clock. But somehow, and against all usual horological practice, the tick and the tock were irregular. Tick tock tick ... and then the merest fraction of a second longer before ... tock tick tock ... and then a tick a fraction of a second earlier than the mind’s ear was now prepared for. The effect was enough, after ten minutes, to reduce the thinking processes of even the best-prepared to a sort of porridge. The Patrician must have paid the clockmaker quite highly.

-- Feet of Clay, by Terry Pratchett

The challenge

Write a function or a program that alternatively outputs "tick" and "tock" every second. There is a 1/5 chance that the tick or tock should be slightly faster or slightly later than expected, with a 50/50 chance between it being early or late. The time difference should be 0.2 seconds.

The clock should still keep accurate time: that is, if a tick or a tock is early or late, the next tick or tock should still be on-time. The clock itself should not "drift" because of the displaced ticks or tocks.

Rules

The usual rules and loopholes apply.

This is code golf: shortest code wins.

\$\endgroup\$
  • 3
    \$\begingroup\$ Please give an objective definition of "small, but noticeable". I can say 0.01s are noticeable to me because I am Data (or Lore) \$\endgroup\$ – wastl Jul 22 '18 at 13:00
  • 1
    \$\begingroup\$ I think an important part should be that, overall, the program should still keep accurate time \$\endgroup\$ – Jo King Jul 23 '18 at 2:58
  • \$\begingroup\$ I agree - I'll rewrite that part so that the clock still keeps accurate time. \$\endgroup\$ – Ciaran_McCarthy Jul 23 '18 at 7:54
  • \$\begingroup\$ Going Postal - "Sometimes the tick was just a fraction late, sometimes the tock was early. Occasionally, one or the other didn’t happen at all." <- any chance of including the bolded part (emphasis mine)? Also, is there a 1/5 chance of any alteration (fast or slow), or 1/5 chance of fast and another 1/5 of slow? \$\endgroup\$ – boboquack Aug 3 '18 at 11:43
  • \$\begingroup\$ @boboquack and if tock is omitted, is the next output a tick or a tock? \$\endgroup\$ – JayCe Aug 14 '18 at 20:25
  • \$\begingroup\$ @JayCe I would assume a tick though that's up to the OP of course. \$\endgroup\$ – boboquack Aug 14 '18 at 22:26
  • \$\begingroup\$ I would say that if a tock is omitted, the next output would be a tick, and vice versa. Would the Going Postal requirement be a good one for a bonus critera, so -10% for omitting the tick or the tock? Or would it be better as part of the normal requirements? \$\endgroup\$ – Ciaran_McCarthy Aug 16 '18 at 7:40
1
\$\begingroup\$

Looking for feedback on my first question.

Title: Largest Left-Truncatable Prime in Base \$b\$ (A103443)

Introduction

Numberphile recently posted a video about truncatable primes, and the concept seems like it would make a good base for a number of good code golf exercises. I explain the concepts below, but watch the video only if you want ideas about an algorithmic process for finding them.

A left-truncatable prime in base \$b\$ is a prime \$p\$ such that

  • all the digits of \$p\$ in base \$b\$ are nonzero, and
  • when any number of leading digits of \$p\$ when written in base \$b\$ are removed, the result is still a prime. (That is, every suffix of \$p\$ when written in base \$b\$ is a prime, when still interpreted in base \$b\$).

For example, \$1223\$ is a left-truncatable prime in base \$10\$, since \$1223\$, \$223\$, \$23\$, and \$3\$ are all prime; \$1223\$ is also a left-truncatable prime in base \$4\$, since \$1223\$, \$223\$, \$23\$, and \$3\$ are all prime when considered in base \$4\$ (in base \$10\$ they are \$107\$, \$43\$, \$11\$, and \$3\$, respectively). OEIS sequence A024785 is a list of all left-truncatable primes in base \$10\$.

There are many variants on this concept, but this is all you need for this challenge. This concept also appeared in this challenge from two years ago.

Challenge

Your challenge is to find the largest left-truncatable prime in base \$b\$. You can show (from this paper I believe) that there are only finitely many left-truncatable primes for a given base, so the largest one exists. Here it is instrumental that we require these primes to have all nonzero digits; otherwise, there would be no largest one.

For example, the largest left-truncatable prime in base \$10\$ is 357686312646216567629137, as mentioned in the above video. These are found in A103443.

Your program must input an integer \$b \geq 3\$, and output an integer written in base \$10\$ which is the largest left-truncatable prime in base \$b\$ (indeed, one must always exist as well). Your program/function should work for any input \$b\$ your language supports.

This is code-golf, so the shortest answer wins! No standard loopholes, but built-in primality testing is allowed.

If your program fails because it would require integers that exceed your language's max integer, then state so in your solution; these solutions are still allowed, but solutions that aren't limited by the language's max integer are better. Alternatively, if you are restricted by a max integer, give the largest left-truncatable prime base \$b\$ that is smaller than this max integer.

Example Input and Output

Input:

10

Output:

357686312646216567629137

See A103443 for more test cases.

Remember that \$1\$ is not a prime.

\$\endgroup\$
  • \$\begingroup\$ Hi, welcome to PPCG! This looks like a great and well-formatted first challenge, so not much to add. The only thing is that I would add some more test cases to the challenge description itself. I doubt the link oeis.org/A103443 will ever be gone, but challenges should be self-contained as much as possible. \$\endgroup\$ – Kevin Cruijssen Jul 31 '18 at 10:04
  • 2
    \$\begingroup\$ Looks pretty much fine to me as a pure golf. +1 on add a couple more test cases. Note, however, that it is likely that solutions, especially those in golfing languages, may well be posted that do not run for bases above some pretty low limit (e.g. 6) due to the implementation. In cases like this some like the challenge to remain pure-golf and allow this while others choose to require some observed run requirement - e.g. "must've been observed to run for base 12 within 60s (post online interpreter link or local output)". Totally up to you on that (anyone else here have an opinion?). \$\endgroup\$ – Jonathan Allan Jul 31 '18 at 12:04
  • \$\begingroup\$ I feel like this is going to work sort of like a breadth first search. \$\endgroup\$ – fəˈnɛtɪk Aug 3 '18 at 18:34
1
\$\begingroup\$

Locate Substring

This is not a challenge yet, just a place to write down an idea.

Given some finite binary string \$S\$, we can try to find the minimal length \$n \in \mathbb N\$ such that we can uniquely locate each contiguous substring \$ T \$ of \$ S \$ that has length \$ n \$.

Example

Let \$ S = 01000110 \$. Then surely \$ n > 1\$. But we also immediately see that \$ n > 2\$ because for instance the substring \$T = 01\$ appears twice in \$ S = \color{red}{01}00\color{red}{01}10\$. But all substrings of length \$ n=3 \$ are distinct, these are in fact (in the order they apppear from left to right) \$ \{ 010, 100, 000, 001, 011, 110 \} \$. This means that \$ n=3 \$ is minimal. [end of example]

Alternatively given some \$ n \$ one might ask to find the longest sequence \$ S \$ such that all substrings \$ T \$ of length \$ n \$ are uniquely locatable.

\$\endgroup\$
  • \$\begingroup\$ Interesting idea, though I think the alternative would create more interesting solutions. \$\endgroup\$ – ბიმო Jul 28 '18 at 15:19
  • \$\begingroup\$ @OMᗺ I think the solution to the "alternative" are the de-Bruijn sequences, which we've covered here. \$\endgroup\$ – flawr Jul 31 '18 at 20:58
  • \$\begingroup\$ Ah true, that would be a dupe. \$\endgroup\$ – ბიმო Jul 31 '18 at 21:07
1
\$\begingroup\$

Order times fully written out in English, alphabetically

A 12h format time of day can be fully written out in English according to the following rules:

  1. a word from one to twelve;

  2. a space;

  3. optionally a word from one to fifty-nine followed by a space;

  4. the "word" AM or PM.

Examples:

 1:31 AM  => "one thirty-one AM"
11:12 PM  => "eleven twelve PM"
 4:00 AM  => "four AM"

Challenge

The challenge is to take a list of 12h format times and order them alphabetically by the way they are fully written out in English.

Input and output format is flexible. Output can either be the times themselves or their fully written out in English versions.

This is . Shortest in bytes for each language wins. Standard loopholes forbidden.

Test cases

[ "1:31 AM", "11:12 PM", "4:00 AM" ]   =>   [ "11:12 PM", "4:00 AM", "1:31 AM" ]

More test cases can be added if there is interest.

I'm mainly concerned this might be a dupe. I couldn't find one.

\$\endgroup\$
  • \$\begingroup\$ There's no real pattern there, so it will most likely be answers sortBy(inputs, key=toEnglishString), I think. Why not just ask for translating it to English? \$\endgroup\$ – ბიმო Aug 3 '18 at 3:46
  • \$\begingroup\$ A dupe of codegolf.stackexchange.com/q/71203/80010 I believe \$\endgroup\$ – JayCe Aug 14 '18 at 20:15
1
\$\begingroup\$

Edit distance for sparse strings

The input to this challenge will be two strings of length one million each. Each string contains only zeros and ones. However each string will contain at most 100 ones and so will be represented by a sorted list of integers. The integers will indicate where the ones are.

Example of input

[ 42394, 108181, 154190, 217161, 301607, 379951, 412651, 623862, 624712, 783863]
[ 42393, 108181, 154189, 267161, 301608, 379951, 412651, 623862, 624713, 783863]

We want to compute the Levenshtein distance between these two strings. However, the standard algorithm will take around 10^12 time which is too slow.

Task

Your code should take in the two inputs and output the edit distance between the two strings. The only restriction is that your code must be fast enough (and not use too much memory) so that it will complete in less than a minute on a standard desktop PC. In case of doubt, I will test the code on my 8GB AMD processer PC using test inputs that I will create.

Small test cases

To test your code here are some small inputs for strings of length 100 with up to 10 ones.

This pair gives edit distance 8.

[18, 23, 30, 40, 47, 53, 60, 73, 89, 94]
[21, 23, 39, 48, 53, 59, 60, 89]

This pair gives edit distance 8

[19, 25, 26, 40, 43, 62, 74, 75, 85, 89]
[10, 26, 27, 28, 44, 70, 74, 75, 76, 86]

This pair gives edit distance 7

[ 9, 17, 18, 29, 45, 50, 57, 64, 80]
[ 2, 16, 23, 27, 32, 43, 49, 56, 63, 79]

This pair gives edit distance 6

[ 3,  9, 12, 33, 39, 49, 55, 72, 84, 94]   
[ 3,  9, 29, 40, 41, 72, 84, 94]

\$\endgroup\$
  • \$\begingroup\$ I don't think they are closely related. \$\endgroup\$ – Anush Aug 5 '18 at 16:18
1
\$\begingroup\$

Make a reversible formula

For the purposes of this question:

  1. a basic formula \$ y = f(x) \$ takes one of the following forms:

$$ x \\ g(x) + c \\ c + g(x) \\ g(x) - c \\ c - g(x) \\ g(x) c \\ c g(x) \\ \frac {g(x)} c \\ \frac c {g(x)} $$

where \$ g(x) \$ is a basic formula;

  1. a reversible formula \$ y = f(x) \$ takes one of the following three forms:

$$ \begin{align} y = x & \implies x = y \\ y = c - g(x) & \implies x = g^{-1}(c - y) \\ y = \frac c {g(x)} & \implies x = g^{-1} \left ( \frac c y \right ) \end{align} $$

where \$ g(x) \$ is a reversible formula whose reverse is \$ g^{-1}(x) \$ according to the above rules and \$ c \$ is a non-negative integer. A simple example of a reversible formula would be the expression \$ y = \frac 1 {1 - x} \$ whose reverse is \$ x = 1 - \frac 1 y \$.

Your challenge is to take a basic formula and express it as a reversible formula. The following transformations are allowed:

$$ \begin{align} \left . \begin{array}r x + c \\ c + x \end{array} \right \} & \implies c - (0 - x) \\ x - c & \implies 0 - (c - x) \\ \left . \begin{array}r x c \\ c x \end{array} \right \} & \implies \frac c {\frac 1 x} \\ \frac x c & \implies \frac 1 {\frac c x} \end {align} $$

(Note that the strict domain of the resulting formula may exclude some values not excluded in the original formula, but the limit of the formula should be equivalent to the original formula.)

Of course we're dealing in string equations so you'll be using * and / instead. Examples:

(x + 1) * 2 => 2 / (1 / (1 - (0 - x)))

x * 2 + 1 => 1 - (0 - 2 / (1 / x))

Do not include extraneous parentheses in your result.

This is , so the shortest submission that breaks no standard loopholes wins!

\$\endgroup\$
  • \$\begingroup\$ What's the associativity of -? \$\endgroup\$ – user202729 Aug 12 '18 at 11:46
  • 1
    \$\begingroup\$ @user202729 Normal left associativity. \$\endgroup\$ – Neil Aug 12 '18 at 12:18
  • \$\begingroup\$ What are the rules for spaces in expresisons? \$\endgroup\$ – user202729 Aug 12 '18 at 14:27
  • \$\begingroup\$ @user202729 You don't need to support spaces. They're just there for legibility. \$\endgroup\$ – Neil Aug 12 '18 at 19:48
  • \$\begingroup\$ @Neil Cool Challenge! Very interesting \$\endgroup\$ – Don Thousand Aug 12 '18 at 21:02
  • \$\begingroup\$ @Rushabh Comments should only be used for improvement/clarification. For other purposes, use different tools, i.e., flags, votes, answers. \$\endgroup\$ – user202729 Aug 13 '18 at 6:50
  • 1
    \$\begingroup\$ I find this rather hard to understand, perhaps because it fails to distinguish equations from expressions, calling both formulae. I'm not even sure whether part 2 is talking about transformations between equations or about Boolean expressions. It would perhaps be clearer if all equations were removed and expressions were defined using a grammar in BNF. \$\endgroup\$ – Peter Taylor Aug 13 '18 at 11:00
1
\$\begingroup\$

Should I index like this or like that?

Challenge

Let's take a 0-indexed array of length \$l\$. You can index into it with \$i\$, where \$-l\le i<l\$, and the returned element is the element in position \$[i<0]\times l+i\$ (\$[\dots]\$ is the Iverson bracket).

In some cases, it's shorter to use a negative index instead of a positive one, counting the minus sign and the digits as bytes. For example, if we want the \$102\$th element of an array with \$104\$ elements, indexing with \$101\$ and \$-3\$ will both give the same result. However, if we write the numbers in code, 101 is 3 bytes long, while -3 is 2 bytes long, so we prefer -4. In other cases, using a negative index is counterproductive (for a code golfer). Such an example is the will to obtain the \$4\$th element of a \$10\$-element array. In this case, we can use \$3\$ and \$-7\$, but -7 is longer than 3, so we'll choose 3 instead.

Given two inputs \$l\$ and \$i\$, where \$l>0\$ (it doesn't make sense to index into an empty array) and \$0\le i<l\$ (or \$-l\le i<0\$, be consistent), your job is to determine whether positive or negative indexing is better for code golfing purposes. In case both are of the same length, you may return either decision, even inconsistently. The returned value must be one of two distinct and consistent values, defined by the answerer.

Of course, using standard loopholes isn't fun, so, if you do use any, then, sorry, your answer isn't valid. ;-)

Test cases

Here, 1 is used for negative indexing and 0 for positive. I also always prefer using positive indices, but you may prefer otherwise.

l     i           (actual index)
----- ----- ----- -----
    1     0     0     0
   10     9     0     9
 1000   999     1    -1
10000  9755     1  -245
  101   100     1    -1
  150   141     1    -9
  150   140     0   140
\$\endgroup\$
  • \$\begingroup\$ Could we output True/False values instead? \$\endgroup\$ – Don Thousand Aug 19 '18 at 0:26
  • \$\begingroup\$ @RushabhMehta True and False are two distinct values; however, outputting "truthy or falsy" but not necessarily consistent values isn't okay. The actual truthiness of the returned value doesn't matter. \$\endgroup\$ – Erik the Outgolfer Aug 19 '18 at 0:38
  • \$\begingroup\$ Ugh...there goes my lean solution \$\endgroup\$ – Don Thousand Aug 19 '18 at 0:39
  • \$\begingroup\$ @RushabhMehta Sorry, but I consider truthiness, as defined by consensus, to be a tad bit unclear, since many languages don't have only one feature you can call an "if construct". \$\endgroup\$ – Erik the Outgolfer Aug 19 '18 at 0:42
1
\$\begingroup\$

Fuzzy Circles

Edit

I don't actually like this challenge all that much. Anyone who wants it can have it, else I'll get rid of it.

Background

For a real number x, let ⌊x⌋ be the greatest integer less than or equal to x.

Challenge

Given an input n, find the minimum radius of the circle such that all points that satisfy the following equation are on its interior or border.

⌊x⌋^2+⌊y⌋^2 = n

Input: A real number n

Output: A real number representing the radius of the smallest circle that contains in its interior or border all points that satisfy ⌊x⌋^2+⌊y⌋^2 = n.

Note: The precision expected in this challenge is two decimal places, both for the input and output.

This is a challenge.

Test Cases (More to be added):

25->5.70

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

Knightmare in 1024 bytes of (JavaScript?)


Board

The board is a 16x16 grid of squares. It does not wrap, so the outer edges are an impassable boundary.

Pieces

Each piece is like a Chess knight, and will be referred to as a knight. It moves to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally.

Chess board showing a knight and its moves

A knight can move to any of these squares, regardless of whether it is occupied. There is no limit to how many knights may occupy the same square at the same time.

Players

This is a 2 player game. Each player has 16 knights. Knights cannot be removed from the board so there will still be 16 knights per player at the end of the game.

Turns

Each turn both players move all 16 of their knights simultaneously (that is, all 32 knights move at the same time).

Costs

Each square has a cost, which is a non-negative integer, initially set to zero. Each time a knight visits a square, the cost of that square is increased by 1. To be explicit, if N knights land on a square in the same turn, that square's cost is increased by N.

Penalties

After each turn, each knight incurs a penalty, which is the cost of the square it occupies, plus the number of other knights occupying the same square (regardless of whether they are friend or foe).

The player's cumulative penalty is zero at the start of a game, and is increased by each knight's penalty each turn (for all 16 of its knights).

Winning

A game ends after 1024 turns. The winner is the player with the lowest cumulative penalty.

Input

The player is supplied with:

  • an array showing the cost for each square
  • an array showing the number of its own knights for each square
  • an array showing the number of its opponent's knights for each square
  • an array showing the total knights for each square
  • an array of coordinates for its own knights
  • an array of coordinates for its opponent's knights
  • its own cumulative penalty
  • its opponent's cumulative penalty
  • the turn number

Output

The player responds with a move for each of its 16 knights. Each move is a number from 0 to 7, indicating the direction to move, numbered clockwise from the top. The response must be received within 5ms.

Invalid moves

Since the edge of the board is impassable, sometimes there will be fewer than 8 valid moves available for a given knight. If an invalid move is given, it will be reflected vertically and/or horizontally to give a valid move, and that move will be made instead. This means every knight will move every turn - none will ever stand still.

Code

Each entry provides the body of a JavaScript function that is no more than 1024 bytes.


Sandbox questions

  • I'm not settled on which language to use yet. I like the idea of using a different language for each KotH. I'm considering maybe Japt or APL for this one. Ideally something terse since golfing is part of the challenge here.
  • Fixed starting configuration (for example, players in a line along opposite edges of the board), or random initial placement?
  • Leaning towards a board that does not wrap. Any reasons to avoid this?
  • I've put placeholder values for the number of bytes, the size of the board, and the number of knights per player. Any feedback on how to improve these values welcome.
  • I'm not sure whether to make staying still a valid move. I'd prefer to keep it simple and have 8 possible moves with no possibility of staying still.
  • I'm currently deciding between the penalty being the cost plus the number of other knights on the same square, or the cost times the number of knights on the square.
  • I need to settle on input and output that are suitable for both golfing the contestant code and keeping things running reasonably quickly.
\$\endgroup\$
  • \$\begingroup\$ "cost plus number of other knights" means other knights aren't that much of a hindrance, since the cost of visiting a square with a knight in it is only one point more than visiting a square that was previously visited. (And I would expect most squares to have been previously visited multiple times.) "cost times number of other knights" makes it very different, as it becomes almost entirely about avoiding other knights, much more than avoiding previously visited squares. I'm not sure which is best, just pointing this out. \$\endgroup\$ – Nathaniel Apr 22 '18 at 15:00
  • \$\begingroup\$ Also: when I read "knightmare", I imagined a child wandering through computer generated rooms wearing a helmet that you can't see out of, guided by Treguard and his sidekick Pickle the Elf. This may be because I am a British person of a certain age. \$\endgroup\$ – Nathaniel Apr 22 '18 at 15:02
  • \$\begingroup\$ Maybe I need something in between then. Will give it some more thought \$\endgroup\$ – trichoplax Apr 22 '18 at 15:08
  • \$\begingroup\$ I am also a British person of a certain age. I may change the title before posting... \$\endgroup\$ – trichoplax Apr 22 '18 at 15:08
  • \$\begingroup\$ I feel like there's very little room for strategy here. Moving to the smallest-cost room will pretty much always be the best strategy, and if it's not, it will only be wrong by a couple of points (and a single-turn look-ahead will greatly mitigate that) I think that there will be too much randomness (in how the enemy moves) to really make this interesting. \$\endgroup\$ – Nathan Merrill Apr 22 '18 at 15:41
  • \$\begingroup\$ I don't personally think challenges should impose a maximum byte count. Is there a reason that only allowing 1kB is important? \$\endgroup\$ – Kamil Drakari Apr 22 '18 at 17:16
  • \$\begingroup\$ I'm against minimum required scores in code golf, agreeing entirely with Martin's arguments. In that context the byte count is the score, and I wouldn't want to exclude anyone, or prevent someone from posting a long answer that can gradually be improved over time. I see this KotH as different. The limit is not intended as a barrier to entry. I want to choose a limit that will allow anyone to post a basic entry, and then gradually improve it over time as they find ways to fit more in. \$\endgroup\$ – trichoplax Apr 22 '18 at 19:06
  • \$\begingroup\$ I want a KotH that has some of the aspects of a code golf challenge. That was the initial idea, and the knights came later. If they are not considered a good fit then I will consider changing the game to something that fits a byte limited challenge better. The other option is to have no byte limit but make the number of bytes somehow penalise the player, whether in increasing their score or restricting their abilities within the game. That seems harder to get right, so I'm going with a byte limit as the simplest way of including short code as a game constraint. \$\endgroup\$ – trichoplax Apr 22 '18 at 19:10
  • \$\begingroup\$ @NathanMerrill I've also worried about this. This is part of why I'm considering a significantly increased penalty when sharing a square with other knights, to allow blocking off the opponent knights from lower cost regions. I feel like that will be one of the most important things to fine tune carefully before posting the challenge \$\endgroup\$ – trichoplax Apr 22 '18 at 19:16
  • \$\begingroup\$ Another way of thinking about the byte limit: Code golf has a single fixed task and the byte count varies. This KotH has a single fixed byte count and what people choose to do with it varies. \$\endgroup\$ – trichoplax Apr 22 '18 at 19:18
  • \$\begingroup\$ Contests like Tweetable Mathematical Art have a byte limit but are too broad. The idea with this KotH is to have a byte limit combined with an objective way of measuring competitors against each other, making the requirement very specific (outcompete the others) while leaving the method open. \$\endgroup\$ – trichoplax Apr 22 '18 at 19:22
  • \$\begingroup\$ @trichoplax Your code-golf goals might be better achieved if you make a custom language for this. If you make a more-or-less "flat" language, and score it by the number of lines, then you have the challenge of "fitting stuff in", without resorting to typical golfing. \$\endgroup\$ – Nathan Merrill Apr 23 '18 at 1:34
  • \$\begingroup\$ I think the limited byte count is a good idea, or could be, as long as optimal solutions to the challenge are much too complicated to fit into the available space. (See Paint Starry Night for an example where this worked well, in my humble opinion). That might not be the case here though, as the challenge might not require very complicated strategies, and 1024 bytes is pretty huge even for Javascript. (In Starry Night most competitive entries used most of that space for data rather than code.) \$\endgroup\$ – Nathaniel Apr 23 '18 at 2:05
  • 1
    \$\begingroup\$ What I don't want is a KotH where you write the same solution you would have without the limit, and then have the extra task of golfing it. I want the limit to lead to innovation, not just extra work \$\endgroup\$ – trichoplax Apr 23 '18 at 6:11
  • 1
    \$\begingroup\$ JS-only? That's a bad enough restriction at the best of times, but when you're also imposing tight time limits it's worse. \$\endgroup\$ – Peter Taylor Apr 25 '18 at 12:01
1
\$\begingroup\$

Golf me some Golf

Write a program to play Golf solitaire!
(I'm somewhat surprised that I haven't seen this pun yet.)

How to play

Golf uses a standard 52 card deck. Play begins with 7 stacks of 5 cards each, one card forming the foundation, and the remaining 16 cards forming the stock. There are two legal moves:

  • Move a card from the top of a stack to the foundation (must be one rank higher or lower)
  • Draw the top card of the stock and place it on the foundation

The number of cards remaining in the tableau when you run out of moves is your score, with zero being a perfect game.

To make things easier, queens may be played on kings, and aces and kings can be played on each other. Also, while the stock is normally face-down, you will be able to read it all at once.

Rules

The input to your program will be 7 lists of 5 cards representing the tableau (with the last cards on top) plus 1 list of 17 representing the stock (the last card being the foundation). These lists can be flattened as desired (you can take 1 list of 35 and 1 list of 17, or just 1 list of 52). Cards are represented as numbers 0-12.

Your program should output a list (or string) of numbers 0-7 representing the moves in a game of Golf. The numbers 0-6 represent playing a card from a column to the foundation, and 7 represents drawing a card from the stock. Any illegal moves (including playing from an empty column or stock) will disqualify your program.

Your score is the number of bytes in your program plus 2 bytes per card left on the stock after running through the 18 games in the scoring set. The program with the lowest score wins.

Test cases

Example output: (coming soon)

Scoring set: (coming soon)

All games in the scoring set are solvable.


Sandbox questions:

  • Is code-golf appropriate for this scoring metric, or would code-challenge be more appropriate?

  • Should I do away with the scoring metric, and just require the games to be solved completely?

  • Would it be more interesting to include some unsolvable games in the scoring set to make programs handle that case gracefully?

\$\endgroup\$
  • 1
    \$\begingroup\$ Honestly, I think code-challenge would be more suitable for this. Code golf usually isn't good for things like this. I'd say best solitaire player wins. \$\endgroup\$ – Redwolf Programs Aug 26 '18 at 15:16
1
\$\begingroup\$

Permutation Encoding

Now posted to the main site. Check the revisions log if you want to see the WIP versions.

\$\endgroup\$
  • \$\begingroup\$ IMO it would improve the question to edit in the part about Discord so that it is a motivated problem rather than an arbitrary challenge. All of the elements of this have already been covered by earlier challenges (bijective bases and permutation indices), but the variation in lengths probably push it out of duplicate territory. \$\endgroup\$ – Peter Taylor Aug 29 '18 at 8:33
  • \$\begingroup\$ I put the backstory at the bottom. I thought it had lower priority than the problem itself. I'm also concerned that if I put it at the top, it'd give the impression that Discord reactions is the problem rather than the actual problem I posted. Even if it's clear they're distinct, it might still be confusing since the actual problem is very different from its inspiration. // Also, there's some room for creativity here, I used a numbering approach but I'm sure more clever encoding methods are possible and golf better. There's 2.16E148 possible original and 2.81E148 possible encoded strings. \$\endgroup\$ – EPICI Aug 29 '18 at 17:32
  • \$\begingroup\$ Ah, I misinterpreted "Extras" as heading some information which you intended to be only for the sandbox. \$\endgroup\$ – Peter Taylor Aug 29 '18 at 17:51
  • 3
    \$\begingroup\$ If you've posted this to main, could you please clear and delete it to clear up clutter? Thanks! \$\endgroup\$ – Jo King Sep 4 '18 at 6:04
  • \$\begingroup\$ Please delete your challenge proposal to remove clutter. \$\endgroup\$ – Jonathan Frech Sep 18 '18 at 21:29
1
\$\begingroup\$

Distinct Dice Sum Algorithm

From a puzzle on Brainden. Paraphrasing,

What is the best set of 8 sided dice, each identical, such that 3 dice can generate 120 distinct sums? "Best" means the minimum highest sided die configuration.

With 7 sided dice, the best possible sides for each (identical) die is: 1, 2, 8, 51, 60, 79, 83.

For the sake of discussion, use sides=s, and dice=d.

Note1: 120 is the maximum number of distinct sums with s=8, d=3. The formula is:

$$ \frac{(s+d-1!)}{(s-1)!(d)!} $$

Similarly, for s=7, d=3, the formula gives 84. And brute force shows that a side of at least 83 is required for this easier problem.

Note2: The lowest numbered side is always 1 for an optimal solution to the original question. (See comments.)

My question is, "What's the fastest algorithm to discover the minimum highest sided die for maximum distinct sums?".

Specifically, is there some existing algorithm, or better yet, formula, for the minimum highest sided die? For determining all sides?

While there are obvious choices for languages, I'm not interested in that. I'm interested in the best algorithm possible in general. A sketch of the algorithm with the best (smallest) Big-O score wins.

Complexity of answers should be expressed by Big-O notation, e.g., M(s) = O(???), with d=3. Ties will be broken according to number of dice, i.e., M(s,d) = O(???).

As a puzzle toy to idle time some years ago, I wrote a brute force solver. Unfortunately, for (s=8, d=3), and even knowing an upper limit, my program never completed the search (uptime was an issue).

\$\endgroup\$
  • 3
    \$\begingroup\$ To turn this into a challenge, you'll have to pick an objective winning criterion. fastest-algorithm would work if you want to minimize asymptotic time complexity, but since the complexity will depend on s and d, you'll have to combine them somehow. \$\endgroup\$ – Dennis Aug 28 '18 at 14:08
  • 1
    \$\begingroup\$ Exactly 120 distinct sums or at least 120 distinct sums? \$\endgroup\$ – Peter Taylor Aug 30 '18 at 10:12
  • 2
    \$\begingroup\$ "it would be preferable to word your challenge more like a challenge and less like a help request." – quote Dennis. \$\endgroup\$ – user202729 Aug 30 '18 at 13:39
  • \$\begingroup\$ The challenge can be trivially solved in linear time in the output (which is optimal time), because note that the largest face need to be at least 41 (otherwise 3 ≤ sum ≤ 120 and there can't be 120 values, assuming all values are positive integers), therefore for all s ≥ 41 just output 1 ... 41 and a bunch of other 1s to fill up the faces. Not interesting. \$\endgroup\$ – user202729 Aug 30 '18 at 13:46
  • \$\begingroup\$ @user202729 I don't think that works. You have 8 faces to work with, which is less than 41. \$\endgroup\$ – Nathan Merrill Aug 30 '18 at 20:46
  • \$\begingroup\$ @NathanMerrill No, you have s faces to work with. If s<41 just brute force it (O(1)). Otherwise use the algorithm above. \$\endgroup\$ – user202729 Aug 30 '18 at 23:54
  • \$\begingroup\$ @user202729 Right, for s>41, it's trivial. What is not trivial is less than 41, which I don't see the algorithm for. Which algorithm are you talking about? \$\endgroup\$ – Nathan Merrill Aug 31 '18 at 0:41
  • \$\begingroup\$ @NathanMerrill Note that the challenge requires smallest asymptotic complexity, not runtime. All (correct) algorithm which only operates on bounded input works in O(1), by the definition of "asymptotic". \$\endgroup\$ – user202729 Aug 31 '18 at 0:52
  • \$\begingroup\$ @user202729 True, but it is trivial to increase 120 as well, to provide a way for measuring the asymptotic nature of the algorithm. \$\endgroup\$ – Nathan Merrill Aug 31 '18 at 0:54
  • \$\begingroup\$ @NathanMerrill Then the challenge needs to be edited to explicitly specify that. \$\endgroup\$ – user202729 Aug 31 '18 at 1:01
  • \$\begingroup\$ @user202729 perhaps, but I could see an argument that the 120 is useful to provide a solid ground for the algorithm, as long as they indicate that it is arbitrary. \$\endgroup\$ – Nathan Merrill Aug 31 '18 at 1:03
  • \$\begingroup\$ 120: For s=8, d=3, 120 is the maximum number of distinct sums. I believe the formula is M=((s-1)+d)!/((s-1)!d!). Not sure how to write that well in a comment, but sCd with repetitions. \$\endgroup\$ – Quantum Mechanic Aug 31 '18 at 15:25
  • \$\begingroup\$ Big-Oh notation does not assume a fixed input. If the input is fixed, any algorithm can be said to be O(1), which is unhelpful. For example, f(a) = O(a^2). It's often harder to describe this with more than one variable, but it might be f(a,b) = O(max(a,b)^2). \$\endgroup\$ – Quantum Mechanic Aug 31 '18 at 16:01
  • \$\begingroup\$ @QuantumMechanic for scoring the algorithms, I think you could assume a constant d, but as a tie-breaker, include d. \$\endgroup\$ – Nathan Merrill Aug 31 '18 at 16:13
  • \$\begingroup\$ I think there's an implicit assumption that the smallest permitted value on the side of a die is 1, but that should be made explicit. \$\endgroup\$ – Peter Taylor Sep 5 '18 at 11:09
1
\$\begingroup\$

What is the simplest reversible circuit that computes conjugacy of transpositions?

,,

Motivation

Reversible computation refers to computation in which little or no information is deleted. Reversible computation a major component of quantum computation, and reversible computation is potentially many times more energy efficient than conventional computation. I want to know how easy it is to compute the conjugacy of transpositions reversibly?

Challenge

Let T5 be the set of all transpositions on the set {1,2,3,4,5}. Let * be the conjugacy operation on T5 defined by x * y=xyx^(-1) (here concatenation denotes the group operation). In other words, the underlying set of T5 consists of all 10 pairs (a,b) of distinct numbers from {1,2,3,4,5} and where we declare (a,b)=(b,a). The operation * is the unique operation on the underlying set that satisfies

  • (a,b) * (c,d)=(c,d),
  • (a,b) * (b,c)=(a,c),
  • (a,b) * (a,b)=(a,b)

whenever a,b,c,d are distinct.

What is the simplest n bit input reversible circuit C along with an injective function R:T5->{0,1}^n such that C(R(x),R(y))=(R(x),R(x*y)) for all x,y in T5?

The gate cost of a reversible circuit shall be the sum of the costs of every individual logic gate in the reversible circuit.

Here is the price chart per logic gate (see this link for a description of the logic gates) along with a description of the reversible gates.

Each SWAP gate (x,y)->(y,x) will have a cost of 0.

Each NOT gate x-> NOT x shall have a cost of 1.

Each CNOT gate (x,y)->(x,x XOR y) shall have a cost of 2.

Each Fredkin gate (x,y,z)->(x,(NOT x AND y) OR (x AND z),(x AND y) OR (NOT x AND z)) shall have a cost of 4 (the Fredkin gate can also be described as the reversible logic gate where (0,x,y)->(0,x,y) and (1,x,y)->(1,y,x)).

Each Toffoli gate (x,y,z)->(x,y,(x AND y) XOR z) shall have a cost of 5.

No other gates are allowed.

Observe that each reversible gate has the same number of inputs as it has outputs (this feature is required for all reversible gates).

The complexity of your circuit will be the product of the gate cost or your circuit with the number n which you choose. The goal of this challenge will be to minimize this measure of complexity.

Format

Complexity: This is your final score. The complexity is the product of the number n with your total gate cost.

Space: State the number n of bits that your circuit C acts on.

Total gate cost: State the sum of the costs of each of the individual gates in your circuit C.

NOT gate count: State the number of NOT gates.

CNOT gate count: State the number of CNOT gates.

Toffoli gate count: How many Toffoli gates are there?

Fredkin gate count: How many Fredkin gates are there?

Legend: Give a description of the function R. For example, you may write

(1,2)->0000,(1,3)->0001,(1,4)->0010,(1,5)->0011,(2,3)->0100, (2,4)->0101,(2,5)->0110,(3,4)->0111,(3,5)->1000,(4,5)->1001.

Gate list: Here list the gates in the circuit C from first to last. Each gate shall be written in the form [Gate type abbreviation,lines where the gates come from]. For this problem, we shall start with the 0th bit. The following list specifies the abbreviations for the type of gates.

T-Toffoli gate S-Swap gate C-CNOT gate F-Fredkin gate N-Not gate.

For example, [T,1,5,3] would denote a Toffoli gate acting on the 1st bit, the 5th bit, and the 3rd bit. For example, [T,2,4,6] produces the transformation 01101010->01101000 and [C,2,1] produces 011->001,010->010 and [N,3] produces 0101->0100. For example, one could write [S,7,3],[N,2],[T,1,2,3],[F,1,2,5],[C,7,5] for the gate list.

The gates act on the bit string from left to right. For example, the gate list [C,0,1],[C,1,0] will produce the transformation 01->11.

Sample answer

Complexity: 80

Space: 5

Total gate cost: 16

NOT gate count: 3

CNOT gate count: 2

Toffoli gate count: 1

Fredkin gate count: 1

Legend: (1,2)->00001,(1,3)->00011,(1,4)->00101,(1,5)->00110,(2,3)->01000,(2,4)->01011,(2,5)->01100,(3,4)->01110,(3,5)->10001,(4,5)->10011

Gate list: [N,1],[N,0],[N,4],[S,1,2],[S,2,3],[C,0,1],[C,2,3],[T,3,2,1],[F,4,3,2,1]

Sandbox

\$\endgroup\$
  • 1
    \$\begingroup\$ It would be helpful to define conjugacy, transposition and the group operation. If the challenge is to write a program that does these things then you should specify that along with desired input/output format and winning criterium (e.g. shortest code, fastest code, custom scoring, etc.) \$\endgroup\$ – dylnan Dec 18 '17 at 21:26
  • \$\begingroup\$ is x^(-1) the inverse of x on the group? \$\endgroup\$ – Wheat Wizard Dec 18 '17 at 21:38
  • \$\begingroup\$ Yes. x^(-1) denotes the inverse of x in the group. For transpositions x, we have x^(-1)=x. \$\endgroup\$ – Joseph Van Name Dec 18 '17 at 21:46
  • \$\begingroup\$ It would be helpful if you format the code properly. \$\endgroup\$ – user202729 Dec 19 '17 at 1:22
  • 1
    \$\begingroup\$ "The operation * is the unique operation on the underlying set that satisfies (a,b) * (c,d)=(c,d),(a,b) * (b,c)=(a,c),(a,b) * (a,b) whenever a,b,c,d are distinct." I find that list hard to read with the whitespace as is, but is it incomplete? I think it's missing = (a,b) at the end. For readability, I suggest either using code markup separately for each identity or putting them in an unordered list. \$\endgroup\$ – Peter Taylor Dec 19 '17 at 8:48
  • \$\begingroup\$ I think the C on the right hand side of the condition is wrong. \$\endgroup\$ – Christian Sievers Dec 19 '17 at 21:39
  • 1
    \$\begingroup\$ After reading this a few more times, I find that I'm uncertain as to what branching is allowed. Can I use the same value as input to more than one gate, or is a line "used up" when it goes into a gate? Also, are constant 0 and 1 available, or do they have to be included as extra bits in the output of R? \$\endgroup\$ – Peter Taylor Dec 20 '17 at 11:10
  • \$\begingroup\$ Sorry for being away for a while. I am going to get back to editing this proposed challenge so that it will be up and ready as soon as possible. \$\endgroup\$ – Joseph Van Name Sep 8 '18 at 14:33
  • 1
    \$\begingroup\$ @PeterTaylor. Reversible circuits do not have any branching. Every reversible gate has the same number of input bits as it has output bits. I will clarify this in the post. \$\endgroup\$ – Joseph Van Name Sep 8 '18 at 14:39
1
\$\begingroup\$

Compile Brainbash to BF

Background

BF is an esolang known for it's terseness and small character set. The language operates on a tape of unsigned 8-bit integers, and with a pointer to modify certain values. This pointer starts at the first cell. BF has the following commands available to program with:

+       increment the current cell
-       decrement the current cell
>       move the pointer to the next cell on the right
<       move the pointer to the next cell on the left
.       output the current cell as a character
,       take a character of input
[       begin a loop while the current cell is not zero
]       end that loop

Brainbash is a language similar to BF, but it has two tapes. To deal with this, Brainbash has a "tape focus"; one tape at a time is being worked on. Each tape also has its own pointer. Thus, Brainbash has a few more commands in addition to BF's:

~       swap the tape focus
*       swap tapes and copy the pointer from the previous tape to the next one
{       if the current cell is not zero, execute the code until the next `}` that matches 
}       marks the end an if statement

(There are more commands, but they are not being considered for the purposes of this challenge.)

Challenge

Given a non-empty Brainbash program P, translate that program to BF. That is, output a program Q whose I/O behavior is identical to that of P.

This is a code-golf, so the shortest in program (in bytes) that successfully does this wins.

Specific rules

  • You may assume that each tape is infinite to the right starting at the origin.
  • You may assume that the input is a valid program which has matching { and } and [ and ].

Example Test Cases

(to be introduced)

\$\endgroup\$
  • 1
    \$\begingroup\$ Do the Brainbash tapes wrap, or are they infinite in each direction? Are the Brainfuck commands also Brainbash commands? \$\endgroup\$ – AdmBorkBork Sep 7 '18 at 20:21
  • \$\begingroup\$ What does it mean to translate? Only keep I/O behaviour the same or also some tape structure? \$\endgroup\$ – Jonathan Frech Sep 8 '18 at 9:14
  • \$\begingroup\$ @AdmBorkBork (1) You must support at least 30000 cells to the right of the origin for both tapes (2) Yes \$\endgroup\$ – Conor O'Brien Sep 8 '18 at 16:52
  • \$\begingroup\$ @JonathanFrech Keep I/O behaviour \$\endgroup\$ – Conor O'Brien Sep 8 '18 at 16:53
1
\$\begingroup\$

Make it rotationally-symmetric

(sandbox note: am I using the wrong terminology?)

Background

While looking at this challenge, I notice many some of the answers has 4-fold rotational symmetry. I think it would be convenient to have a program to automatically do it.

Challenge

  • Take input as a string, for which when separated by newlines, all line has equal length. (i.e., the input is rectangular)
  • The output is the smallest square with 4-fold rotational symmetry, where the top-left corner is equal to the rectangle.

Sample input/output

Input:
aba
bab
aba

Output:
aba
bab
aba

Input:
 begin write('left')end.// 
/e .dne)'thgir'(etirw nigeb

Output:
 begin write('left')end.// 
/e .dne)'thgir'(etirw nigeb
/g                        e
.i                       .g
dn                       di
n                        nn
ew                       e 
)r                       )w
'i                       'r
tt                       ti
fe                       ht
e(                       ge
l'                       i(
'r                       r'
(i                       'l
eg                       (e
th                       ef
it                       tt
r'                       i'
w)                       r)
 e                       we
nn                        n
id                       nd
g.                       i.
e                        g/
begin write('right')end. e/
 //.dne)'tfel'(etirw nigeb 

Input:
abc
cde

Output:
abcca
cdedb
ce ec
bdedc
accba

Winning criteria

.

\$\endgroup\$
  • \$\begingroup\$ Could input be a list of strings? \$\endgroup\$ – Kroppeb Sep 13 '18 at 19:39
  • \$\begingroup\$ Do the filler characters have to be spaces? \$\endgroup\$ – dylnan Sep 15 '18 at 0:16
  • \$\begingroup\$ Suggested test case: 'ab\naa' \$\endgroup\$ – dylnan Sep 15 '18 at 0:19
1
\$\begingroup\$

Mini Castle Wars

Note: This is very early draft, and I'll try to develop when I get some time to spare.


Inspired by a previous KOTH based on a card game (but not actually a card game).

Background

This challenge involves a simplified version of the card game Castle Wars.

Game rules

Gameplay

Just like many other card games, Castle Wars is a two-player turn-based game.

Each player starts with 30 units of castle, 5 units of fence, no shield, 2 workers, 8 bricks, 2 magicians, and 8 crystals. Each player is dealt (TBD, 5?) cards from his own deck at start.

Each resource has the following function:

  • Castle: Directly related to the winning condition (see below).
  • Fence: Fences can block the opponent's attack. If the attack would damage the castle by N units, the fence is damaged N units instead. If the fence is less than N units, it becomes zero and the remaining damage is dealt to the castle.
  • Shield: If a castle is shielded, it can nullify any amount of damage to the castle AND the fence, exactly once. Shield can't be stacked.
  • Workers: Each worker produces one brick every turn.
  • Magicians: Each magician produces one crystal every turn.
  • Bricks and Crystals: Every card spends some of these resources to take effect.

Each turn works as follows:

  1. He gets the resources produced by his own workers and magicians.
  2. The player draws a card from his own deck.
  3. He plays a card. If he has enough resources, the card takes effect immediately (including the resources spent). Otherwise, it has no effect whatsoever.
  4. The played card returns to the deck, and the deck is shuffled.

In order to compensate the first-player advantage, resource generation is skipped at the first turn of the game. (TBD)

Cards & deck

A deck consists of at least (TBD) cards, and may include at most (TBD) copies of the same card.

Here is the full list of cards.

  • (TBD, will reflect the actual cards in the game)

Winning condition

A player wins if the opponent's castle is destroyed (0 units or below), or his own castle grows to 100 units or higher. If 100 turns are passed without a player winning, the one with higher castle is declared the winner. Same castle height after 100 turns is a draw.

Tournament

Every bot will have (TBD, even number) matches with every other bot, alternating the first turn.

Controller

TBD. This will ideally be implemented in KOTH-Webplayer.

Submission guide

A submission will look like this:

Deck

'AAAAABBBBBCCDDEXYZ'

Bot

return hand[Math.random()*hand.length|0];

The Deck is a string literal that describes the list of cards your bot will use. The Bot is a snippet that will fit into the following function's body:

function play(hand, myResources, opResources, opPlayed, storage) {
    // function body here
}

The description of parameters:

  • hand is an Array of (TBD) cards in your bot's hand. Your bot's job is to choose a card to play.
  • myResources and opResources are two Objects that have the information of all the resources (the bot's and the opponent's, respectively). Available keys are castle, fence, worker, brick, magician, crystal, shield. (shield is a Boolean indicating whether the player's castle is shielded or not; others are simple numbers.)
  • opPlayed is the card played at the opponent's last turn.
  • storage is an Object you can freely use to store information between turns. It is initially empty ({}).

Meta

  • I originally planned to have a simplified version of the original Castle Wars, but on second thought, the rules are not that complicated and removing some resource types may break the balance of the game (as some interesting cards have to be revised). Would it be good to implement the full game instead?
\$\endgroup\$
  • \$\begingroup\$ Fantastic to see this brewing in the sandbox! Here are a couple pieces of criticism and some potential solutions: a) No tournament type is specified - I'm assuming it's round-robin. This should be added to the spec. a) Is there a need to compensate for the first-player advantage? Surely, a two-way round-robin would be fair enough, no? I'm not sure how large the first-player advantage is, though, so I could be wrong here. c) I've found that there's a handy way to handle persistent storage of things in JavaScript - closures. \$\endgroup\$ – Alion Sep 20 '18 at 9:30
  • \$\begingroup\$ cont. c) I would recommend that all future JS KOTHs required a function factory pattern from players. Here's an example of how that can be useful for entries. Here's how that looks without the closure pattern, and how it negatively affects entries. \$\endgroup\$ – Alion Sep 20 '18 at 9:49
  • \$\begingroup\$ cont. c) For this challenge, this could be additionally useful, since you require players to choose a deck for themselves. The bots could return a {deck, func} object during setup that way. \$\endgroup\$ – Alion Sep 20 '18 at 9:56
1
\$\begingroup\$

Prettify Pixiedust


So Pixiedust is a new esolang I've created. One of the primary points is that it should look like pixie dust—exactly the things that your programs should fix.

Input

The input will be a program written in Pixiedust. Since this is not a challenge to parse the language, it won't be in raw code, but a list of numbers and the strings separating them. The numbers can be taken as the number itself, or their representation in the program.

Randomizing the Literals

For each numeric literal, there are many ways to represent them:

  • Randomly pad the beginning with . characters. It should be an even distribution between padding it to 32 bits and padding it to the base length.
  • If the number is at the end of the line, then take an even split between including and excluding the terminating *.

Scattering

At this point, you should have the lines calculated—let's call this the half-pretty program. For each line of output:

  • Start with a line of pure spaces 4 times the length of the longest half-pretty line.
  • Randomly select spaces from it to replace with program characters. Every combination of spaces should have an equal chance.
  • Replace those spaces with the corresponding characters, without changing the order that they appear in.
  • (Optional) trim off trailing spaces.

Scoring

The winner will be the shortest answer in bytes. Additionally, there will be a 50-rep bounty for the first answer written in Pixiedust.


Examples will be coming once I finish the interpreter and make some submissions to other challenges in Pixiedust.

\$\endgroup\$
  • \$\begingroup\$ Since this is not a challenge to parse the language, I mean, it's not that hard. \$\endgroup\$ – RamenChef Sep 29 '18 at 0:20

You must log in to answer this question.

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