555
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

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

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3939 Answers 3939

1
4 5
6
7 8
132
5
\$\begingroup\$

Split and recombine a number

This challenge has two related parts. Your task is to write two functions/programs as per the below specifications. You may share code across your submissions, the submissions may call one another, and you may even submit a single submission which handles both conversions. In the latter case, conversion direction may be determined by whether the input is a single number vs a list, or by an additional consistent second value (not a function) input.

Part 1

Given a floating point number, return a list with one element per digit of its integer part, if any, and if the number is a non-integer, one additional part which is the fractional part. If the number is negative, negate all elements in the output. If the number is zero, return a 1-element list with a zero in it.

When the result list is recombined as per Part 2, it must be precise to within an absolute or relative error of 10⁻¹⁰, whichever is more permissive.

Part 2

Given a list generated as per Part 1, return the number which would have generated that list in Part 1.

When the result number is split as per Part 1, each element must be precise to within an absolute or relative error of 10⁻¹⁰, whichever is more permissive.

Examples

Part 1 <-> Part 2
-123       [-1,-2,-3]
2.71828    [2,0.71828]
-800.6     [-8,0,0,-0.6]
321.7001   [3,2,1,0.7001]
-0.01      [-0.01]
100        [1,0,0]
0          [0]

\$\endgroup\$
11
  • \$\begingroup\$ (1) Technically infinities are floating point numbers (or, at least, they're not NaNs). What should the output be for an infinity? (2) How about for 1E45? (3) For numbers which are small enough to have a fractional part, what restrictions are there on the precision of the output? E.g. to take the fourth test case, 321.7001 - 321 in IEEE 754 double format gives 0.7001000000000204. \$\endgroup\$ Nov 18, 2018 at 21:18
  • \$\begingroup\$ Do we need the leading 0 in the list? Seems cleaner without it \$\endgroup\$
    – Quintec
    Nov 18, 2018 at 22:11
  • \$\begingroup\$ @Quintec What leading zero? \$\endgroup\$
    – Adám
    Nov 18, 2018 at 22:28
  • \$\begingroup\$ @PeterTaylor I'll exclude infinities. I'm not sure what do do about inexactness. I guess I could allow stopping at 16 digits of precision. Any ideas? \$\endgroup\$
    – Adám
    Nov 18, 2018 at 22:31
  • \$\begingroup\$ Now that I think about it, string output for part one doesn’t make sense. But if it did, then I meant [2, .718] instead of [2, 0.718] \$\endgroup\$
    – Quintec
    Nov 18, 2018 at 22:43
  • \$\begingroup\$ I don't see any reason to reject 0 <-> [], given that 0.01 <-> [0.01]. \$\endgroup\$
    – Bubbler
    Nov 19, 2018 at 1:21
  • \$\begingroup\$ For the precision, how about something in the line of "correct up to absolute/relative precision of 1e-16"? Partly because big numbers stored in double are not accurate even in the integer parts. \$\endgroup\$
    – Bubbler
    Nov 19, 2018 at 1:29
  • \$\begingroup\$ @user202729 Yes, I'll add that. Also, see tolerance text now. \$\endgroup\$
    – Adám
    Nov 19, 2018 at 12:36
  • \$\begingroup\$ @Bubbler Tolerance specs added. \$\endgroup\$
    – Adám
    Nov 19, 2018 at 12:41
  • \$\begingroup\$ Suggested test cases: 4.4 <-> [4,0.4] and 44.44 <-> [4,4,0.44]. Also, can we assume there will not be any unnecessary trailing zeros? I have a working solution, even with workaround for 0 <-> [0], but for 0.0 it outputs [0.0], but vice-versa for [0.0] it outputs 0 instead of 0.0. Hence the question that there won't be test cases like 0.0, 4.0 or 6.4000 with unnecessary trailing zeros. My programming language outputs 4.0 -> [4,0] -> 40 due to the implicit conversion of 0.0 to 0.. \$\endgroup\$ Dec 4, 2018 at 10:44
  • \$\begingroup\$ @Adám FWIW Composed a solution using JavaScript for the specification at this question, and a solution for the specification at the original question (that currently has a bug for two test cases at "Part 2" portion, though is not incapable of being fixed). \$\endgroup\$ Dec 17, 2018 at 23:47
5
\$\begingroup\$

Progress: Updated the rules again, and also add the timed function to the bots.

Sylver Coinage KotH

Sylver Coinage is a 2-player mathematical game that has the following rules:

  1. Two players take turns announcing a natural number each time.
  2. Each number announced must be unrepresentable as the sum of non-negative multiples of the numbers announced before.

    Eg. if the first three numbers announced are \$\{6, 11, 15\}\$, then you cannot announce any numbers representable as \$6n_1+11n_2+15n_3\$, where \$n_1,n_2,n_3\ge0\$. You can announce, for example, \$16\$, though.

  3. The player who announced a number not complying with Rule 2, or the number 1, loses.

Here is a twist -- R. L. Hutchings proved that announcing a prime number as the first play provides a winning strategy for the first player, although the detail of the strategy is not yet known. So I put a restriction here: the first player cannot announce a prime number in the first step. Now the first two numbers will be generated randomly by the driver at the beginning. No more restriction on prime numbers now.

Technical Information

A bot playing the game will have to implement a Python 3 class, extending TimedBot, with two methods: announce() and learn(). announce() should receive a list of numbers (possibly empty) and return a single integer, and learn() should receive two integers (id of the first move and second move) and the complete list of the numbers in the last game played.

Here is a sample implementation. Note: DO NOT use this as your submission -- this sample only serves as a demonstration, and it may announce numbers that violate Rule 2.

class SampleBot(TimedBot):     # must not be changed.
    def __init__(self, id):
        super().__init__()     # must not be changed.
        self.id = id

    def announce(self, list):
        import random
        return random.randint(1, 101)

    def learn(self, first, second, list):
        pass

Test Drive

class TimedBot:
    def __init__(self):
        self.time = 20.0

    def timed(func):
        def f(self, *args):
            import time
            a = time.time()
            b = func(self, *args)
            self.time -= (time.time() - a)
            print(self.time)
            return b
        return f

class SampleBot(TimedBot):
    def __init__(self, id):
        super().__init__()
        self.id = id

    @TimedBot.timed
    def announce(self, list):
        import random
        return random.randint(1, 100001)

    @TimedBot.timed
    def learn(self, first, second, list):
        pass

# very inefficient
def islinearcomb(n, l):
    if len(l):
        for i in range(0, n + 1, l[0]):
            if i == n:
                return [n // l[0]]
            elif len(l) > 1:
                isl = islinearcomb(n - i, l[1:])
                if isl:
                    return [i // l[0]] + isl
    return None

lose = -1
turn = 0
nums = []
bots = [SampleBot(0), SampleBot(1)] # replace with your bots here.

import random
while (len(nums) < 2):
    a, b, c, d = random.randint(1, 10), random.randint(1, 10), random.randint(1, 10), random.randint(1, 10)
    if 2**a * 3**b != 2**c * 3**d and 2**a * 3**b > 100000 and 2**c * 3**d > 100000 and 2**min(a,c) * 3**min(b,d) > 12:
        nums = [2**a * 3**b, 2**c * 3**d]
while lose < 0:
    v = bots[turn].announce(nums)
    print("{0}({1}) announced {2}".format(type(bots[turn]).__name__, bots[turn].id, v))
    w = islinearcomb(v, nums)
    if w:
        str = ""
        for i in range(0, len(nums)):
            if i:
                str += "+"
            str += "{0}*{1}".format(nums[i], w[i] if i < len(w) else 0)
        print("{0}({1}) announced {2} that is equal to {3}".format(type(bots[turn]).__name__, bots[turn].id, v, str))
        lose = turn
    elif v == 1:
        print("{0}({1}) announced 1".format(type(bots[turn]).__name__, bots[turn].id))
        lose = turn
    nums += [v]
    turn = 1 - turn
print("{0}({1}) wins".format(type(bots[1 - lose]).__name__, bots[1 - lose].id))

Restrictions

Each bot will have 20 seconds of time for deciding a move todo: adjustments. Running out time during the move results in a lose, and failing to finish a method within 20 seconds will lead to disqualification and rerun of all 100 rounds with the remaining bots.

Schedule

Submissions will be open until todo: date here. After that 100 complete round-robin rounds will be done. Each pair of bots will compete twice in each round, one with the first bot announcing first, and one with the second bot announcing first. Each win brings 3 points, each draw brings 1 point, and each lose brings no points. The bot with the highest points after 100 rounds wins. The tiebreaker will be as follows:

  1. Points got
  2. Wins achieved
  3. Drawing lots
\$\endgroup\$
14
  • \$\begingroup\$ Probably needs some time limit for responses to prevent solutions which attempt to generate a full game tree. \$\endgroup\$ Dec 17, 2018 at 9:26
  • \$\begingroup\$ @PeterTaylor Oh yes I thought about the time limit but I turned out forgetting to put that ;p \$\endgroup\$ Dec 17, 2018 at 9:31
  • \$\begingroup\$ "The player who announced a number not complying with Rule 2 ... loses." I've been thinking about this. I presume that your intention is that the controller will validate the responses. An alternative would be to say that you don't automatically lose, but to add a type of response where the bot can return a proof that the opponent broke rule 2. Then bot programmers have to make a decision as to how much time to spend trying to show that their opponent lost vs computing a valid response. \$\endgroup\$ Dec 17, 2018 at 20:48
  • \$\begingroup\$ What if a game goes on for a billion turns? \$\endgroup\$
    – isaacg
    Dec 18, 2018 at 1:13
  • \$\begingroup\$ @PeterTaylor I'd say my intention is that the controller will validate the responses. (in the test drive there is the code doing exactly that) \$\endgroup\$ Dec 18, 2018 at 9:29
  • \$\begingroup\$ @isaacg If the number does not start out too large a game should end quite quickly. It is because two coprime numbers already make the number of possible moves finite. But If I pose a criteria on how large a number can at most go, then I'm feared that there may be a problem that the game tree is restricted. \$\endgroup\$ Dec 18, 2018 at 9:30
  • \$\begingroup\$ I'd say: don't restrict the highest move, but give each bot a 'chess clock': they start with (say) 10s, and gain 1 second per move (and pass their clock's time as a parameter). Running over time is an automatic loss, and some percentage of time losses is a disqualification. Playing high moves will quickly exhaust their stock of time if they attempt to calculate extensive game trees, which will force the bots to either play quickly or lower their numbers. Adding a decay function to the time per move will encourage smart bots to play smaller numbers to not run out of time to think. \$\endgroup\$ Dec 24, 2018 at 16:47
  • \$\begingroup\$ @Spitemaster That's a good idea, but what I concerned about on large numbers is that the validation may take too long (because we are solving Diophantine equations in many unknowns) \$\endgroup\$ Dec 25, 2018 at 5:48
  • \$\begingroup\$ Do you realise that guaranteeing that the first two numbers are coprime guarantees that the first player will win with correct play? If you want an interesting game then you should generate the first two numbers randomly as 3-smooth numbers with a GCD which is a multiple of 6 and greater than 12. \$\endgroup\$ Jan 9, 2019 at 11:16
  • \$\begingroup\$ @PeterTaylor Great catch! During discussion only the suggestion of giving two initial numbers was achieved, so I didn't realize that. \$\endgroup\$ Jan 10, 2019 at 0:39
  • \$\begingroup\$ I would remove the submission deadline, why not keep it open and update once a new entry comes? Also you might be interested in this (I adapted the code originally written for another KoTH), the easiest thing will be to enforce a certain formatting on the first line and adapt code_matcher to that formatting, st. that it won't break because everyone is using different formatting. \$\endgroup\$ Jan 10, 2019 at 13:48
  • \$\begingroup\$ @BMO Wow that's a good one! And I saw my code in the source lol BTW for the certain formatting part you mean the lines around class FooBar(TimedBot):? \$\endgroup\$ Jan 10, 2019 at 15:19
  • 1
    \$\begingroup\$ @ShieruAsakoto: Yeah, I added the header to bots.py which will be used, all the users' code will be appended to that and written to auto_bots.py.. Basically you'll only need to checkout the few variables (lines 12-20) and the main (from line 117) to see how it works. About the formatting, yes, that's probably the most sane: Make sure every code starts with class NameOfBot(TimedBot):, all definitions are in that class and it's valid Python 3 code (I updated the code_matcher like this it should work fine). \$\endgroup\$ Jan 10, 2019 at 15:33
  • \$\begingroup\$ If they/you use that bots.py you'll need to manually update the imports or do it inside the bot itself, atm. bots could use random and time, maybe add math too. \$\endgroup\$ Jan 10, 2019 at 15:34
5
\$\begingroup\$

Interleave Invariance

There is an infinite sequence that does not change when interleaved with the natural numbers. Consider these few terms:

1 1 2 1 3 2 4 1

Interleave them with the naturals:

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

As you can see, there is no change in the initial eight. Now, this sequence can be extended indefinitely rather easily by repeating this interleave operation. Your task is to choose and implement one of three output formats:

  1. Take as input a nonnegative integer n and output the nth term of this sequence, zero- or one-indexed (your choice).

  2. Take as input a nonnegative integer n and output the first n terms of this sequence.

  3. Output terms in order forever, starting from the beginning.

For options 2 and 3, there must be no numeric characters and at least one non-numeric character between terms; this separator need not be consistent. 1+1=2 would be fine for input 3. Leading and trailing non-numeric characters are allowed.

Here are the first 64 terms. This is OEIS sequence A003602.

1 1 2 1 3 2 4 1 5 3 6 2 7 4 8 1 9 5 10 3 11 6 12 2 13 7 14 4 15 8 16 1 17 9 18 5 19 10 20 3 21 11 22 6 23 12 24 2 25 13 26 7 27 14 28 4 29 15 30 8 31 16 32 1

Your submission can be a program or a function; "input" and "output" are as defined by the community. Standard loopholes are forbidden.

As this is , the shortest solution (in bytes) wins! Good luck, and happy golfing!


Sandboxy Stuff

Am I clear enough on what the sequence is? Any suggestions for rewording?

Is this a duplicate? I've searched for "interleave" and "3602" and found nothing.

Anything else worth mentioning? What thoughts ya gots?

Thanks to Martin Ender for the output formats, taken almost straight from the Kolakoski challenge.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ related (not a dupe though) \$\endgroup\$
    – dzaima
    Feb 13, 2019 at 19:35
  • \$\begingroup\$ You could consider removing the option to output just the n'th term, making answers output a sequence. Otherwise I think it will be shortest in most languages to take n, halve until non-whole, then add 1/2 (ceiling), rather than use the interleaving property which I think is cooler. \$\endgroup\$
    – xnor
    Feb 15, 2019 at 0:46
  • \$\begingroup\$ It looks like n/(n&-n)/2+1 would work for a lot of languages such as Python. \$\endgroup\$
    – xnor
    Feb 15, 2019 at 1:09
  • \$\begingroup\$ @xnor Do you think removing that option will help much? I can't really think of a case where the solution won't be to wrap your expression in a looping construct if the expression was the shortest. I don't think knowing the history of this function is that helpful to finding the future value. \$\endgroup\$ Feb 25, 2019 at 22:09
  • \$\begingroup\$ @FryAmTheEggman You're probably right, answers would mostly just do the expression in some loop. In Haskell I think the interleaving definition wins out (even with option 1 allowed), but maybe that's just Haskell. \$\endgroup\$
    – xnor
    Feb 26, 2019 at 6:22
5
\$\begingroup\$

Evaluate C−− expression

Your goal is to a evaluate an expression in "C−−" (not this one) which uses only the characters are C and -. C is an variable holding an integer whose initial value you're given, and the - symbol is used in many ways including as a decrement operator:

  • C-- decrements the value stored in C, then evaluates to that value.
  • --C evaluates to C, then decrements the value stored in C.
  • -expr negates the value of the expression expr.
  • expr1-expr2 takes the difference of the two expressions.

Unfortunately, the C−− specification doesn't state how expressions are parsed or in what order parts are evaluated, saying these are "implementation dependent". So, it's up to you. For example, --C---C could be interpreted as -(-(C--)-C) or (--C)-(--C) or others, and each --C might be evaluated before or after other parts of the expression.

Input: A string consisting of C and -, and an integer initial value for C.

The string will be parseable in at least one way. You can take the string as a list of characters, but they must be exactly the characters C and -.

Output: A value this expression could evaluate to.

You don't need to worry about issues with overly large values like overflows or loss of precision.

TODO: test cases

\$\endgroup\$
7
  • 2
    \$\begingroup\$ Can --C---C be parsed as -(-(C-(-(-C))))? \$\endgroup\$
    – H.PWiz
    Apr 13, 2019 at 17:44
  • 2
    \$\begingroup\$ @H.PWiz Yes. Unfortunately, it looks like as is --C, can always be interpreted as -(-C), which is golfier but more boring, so I'll probably restrict the parsing or removing the unary negation option. \$\endgroup\$
    – xnor
    Apr 13, 2019 at 17:50
  • 1
    \$\begingroup\$ @xnor Note: -C is the same as (C-C)-C, but there are no parentheses here so nobody can say it can't also be parsed as C-(C-C). An added rule can be "You can't parse --C as -(-C), as a double negation would be meaningless." \$\endgroup\$ Apr 13, 2019 at 17:55
  • \$\begingroup\$ Do you want to include or exclude simple eval implementations? \$\endgroup\$
    – Phil H
    Apr 29, 2019 at 15:22
  • \$\begingroup\$ @PhilH That's a good question. Eval-style solutions seems pretty boring for C-style languages, but I don't know if there's a clean way to even specify what would be disallowed. I don't have time to work on this challenge, so you're welcome to spruce it up and post it if you want. \$\endgroup\$
    – xnor
    Apr 30, 2019 at 1:05
  • \$\begingroup\$ if the C-- in question is not the one linked, could you link the one you're referring to? You mentioned a C-- specification, so I assume there is one \$\endgroup\$
    – Mayube
    May 3, 2019 at 17:29
  • \$\begingroup\$ @Skidsdev I meant it as a thing I'm making up for the challenge. \$\endgroup\$
    – xnor
    May 3, 2019 at 22:02
5
\$\begingroup\$

An Auction in St. Petersburg

Setup

Mysterious packages are up for auction today. These boxes are unique in that their values are not known until they are opened, and when they are opened, their values follow a unique distribution:

probability    value
0.5               $2
0.25              $4
0.125             $8
0.0625           $16
1/(2^n)       $(2^n)

In total, there are 100 such packages up for auction, to be sold sequentially. At the start, each bot arrives with $20 in their wallet, and the goal is to walk away with more money than anyone else.

During each round in the auction, each bot simultaneously submits a bid. The bot with the highest bid (ties broken randomly) must pay the value of the second-highest bid, after which that winning bot receives an amount of money corresponding to the value of the opened package. This money can then be "reinvested" in future rounds of the auction.

The auction day ends once all 100 packages have been sold, or when any bot's wallet value exceeds 2^31.

I/O format

As input, your bot receives the following info:

  • an array of everyone's current wallet amounts
  • the history of past sale prices (the amount paid, not highest amount bid) and winners

As output, your bot returns an integer between 0 and your current wallet amount.

Tournament format

There will be N=large number of game run according to the above format (100 auction rounds each), and the finishing position of the bots will be averaged across games.

\$\endgroup\$
3
  • \$\begingroup\$ Could you explain why it ends when someone reaches 2^31? \$\endgroup\$
    – Artemis
    Apr 16, 2019 at 3:17
  • \$\begingroup\$ @ArtemisFowl It's mostly to prevent players from having to deal with numbers that don't fit into a 32-bit integer. There's only a 1 in 1 billion chance that a particular package will contain enough money to trigger this condition, I just wanted to clarify how I would handle the "infinite expected value" in practice. \$\endgroup\$
    – PhiNotPi
    Apr 16, 2019 at 14:45
  • 1
    \$\begingroup\$ This seems rather win-more. It just takes one big win to be able to guarantee that you can outbid everyone else for the rest of the game. \$\endgroup\$ Apr 20, 2019 at 21:40
5
\$\begingroup\$

Fix my stuttered words

Posted: Fix my stuttered words

\$\endgroup\$
3
  • 1
    \$\begingroup\$ "You can assume that multiple valid sets of repeated stuttered words only happen from left to right, so fixing "op op op o o o open" would result in "op op op open"." Shouldn't this result in "op open" instead? In the first rule you mention "For example "ope" and "open" both can be a stuttered word for "open"." So since the entire word is valid as stutter, I would think "op op op o o o open" becomes "([op op] op) ([o o o] open)" (([this] ... ) being the stutter, and ([...] this) being the word), thus "op open". \$\endgroup\$ Sep 13, 2019 at 9:45
  • 1
    \$\begingroup\$ I think you meant to give the example "... so fixing "op op o o o open" would result in "op op open"." (so one less op) instead? \$\endgroup\$ Sep 13, 2019 at 9:46
  • \$\begingroup\$ @KevinCruijssen: You are absolutely correct, I have updated the question. Thank you for reading with such a high precision. \$\endgroup\$
    – Night2
    Sep 13, 2019 at 12:26
5
\$\begingroup\$

Add the quotes

Background

There's a terrible problem in my console - the quotes never get included inside the arguments! So, when given this argument:

["abc","def","ghi","jkl"]

it says that the argument is like this:

[abc,def,ghi,jkl]

It would be very nice if you can fix this problem!

Body

Add double-quotes (") in order to surround a word (i.e. something that matches [a-z]+).

[[one, two, three],
[one, two, three],
[one, two, three],
[one, two, three]]

Test cases

[abc,def,ghi,jkl] -> ["abc","def","ghi","jkl"]
this is a test    -> "this" "is" "a" "test"
test              -> "test"
this "one" "contains' "quotations -> "this" ""one"" ""contains"' ""quotations"
But This One Is SpeciaL! -> B"ut" T"his" O"ne" I"s" S"pecia"L!

Rules for the input

  • The words are never capitalized.
\$\endgroup\$
7
  • \$\begingroup\$ Suggested test case: one that starts (and/or ends) with a word (i.e. this is a test -> "this" "is" "a" "test"). \$\endgroup\$ Feb 18, 2020 at 16:00
  • \$\begingroup\$ Another suggested test case: a single word without anything else (i.e. test -> "test"). \$\endgroup\$ Feb 18, 2020 at 16:10
  • \$\begingroup\$ An issue here is that since this I/O is strict, many languages can't actually execute it. GolfScript, for example, can't take in letters in any ways that isn't in quotations. \$\endgroup\$
    – Mathgeek
    Feb 19, 2020 at 20:00
  • 2
    \$\begingroup\$ @Mathgeek No you can - do you know that GolfScript takes the whole STDIN as a string? Example. \$\endgroup\$
    – user92069
    Feb 19, 2020 at 22:55
  • 3
    \$\begingroup\$ Perhaps some testcases that already contain quotes \$\endgroup\$
    – Jo King Mod
    Feb 20, 2020 at 5:24
  • \$\begingroup\$ You have to escape them: [\"abc\",\"def\",\"ghi\",\"jkl\"] \$\endgroup\$
    – S.S. Anne
    Feb 23, 2020 at 19:21
  • \$\begingroup\$ Is this challenge not simply a regex substitution; 22 bytes in vim: :%s/\([a-z]\+\)/"\1"/g? \$\endgroup\$ Feb 25, 2020 at 1:11
5
\$\begingroup\$

Is the input Bl lu ur rr ry?

This is based off this challenge.

Given an input string, check whether the string is blurry.

What's a blurry string?

Take a non-blurrified string abc as an example. You repeat every character of this twice:

aabbcc

And then insert spaces at every odd-even index.

a ab bc c

Then, remove the preceding 2 and succeeding 2 extra characters.

ab bc

As an example, all of these strings are blurry (the empty line stands for an empty string):

"a"   ->
"ab"  ->ab
"abc" ->ab bc
"abcd"->ab bc cd
...

Specification

  • The input string consists purely of printable ASCII characters. The only whitespace it will contain is the space character.
  • You don't have to remove extra characters before the check.
  • Your output can consist of any trailing whitespace, as long as it's possible to tell a truthy result from a falsy result.

Test cases

Here is a program I use to check my test cases.

""          -> True
"ab"        -> True
"ab bc"     -> True
"ab bc cd"  -> True
" b bc cd"  -> True
"ab bc c "  -> True
"a   c cd"  -> True

"a"         -> False
"abc"       -> False
"ab  bc  cd"-> False
"ab#bc#cd"  -> False
"abbccd"    -> False
"a ab bc cd"-> False
"a a ab b b"-> False
"ba cb dc"  -> False
"ba bc dc"  -> False
"FFaallssee"-> False
\$\endgroup\$
7
  • \$\begingroup\$ Shouldn't the reverse version be "un-blur the string"? This is more like a decision-problem version of the blur challenge. \$\endgroup\$
    – null
    Apr 28, 2020 at 3:59
  • \$\begingroup\$ This Challenge to Blurry Vision is like Narcissist to Quine. \$\endgroup\$
    – null
    Apr 28, 2020 at 4:00
  • \$\begingroup\$ @HighlyRadioactive Uh-blur the string seems too easy, therefore I made it a decision problem. So can you find a duplicate for this? \$\endgroup\$
    – user92069
    Apr 28, 2020 at 4:26
  • \$\begingroup\$ I think you meant "un-blur". No, this is probably not a dupe. \$\endgroup\$
    – null
    Apr 28, 2020 at 4:28
  • \$\begingroup\$ Possible duplicate: Is it double speak? \$\endgroup\$ Apr 29, 2020 at 0:51
  • \$\begingroup\$ @mathjunkie Not really. This challenge is about consecutive characters separated by consistent spaces. (The spaces may or may not be there.) \$\endgroup\$
    – user92069
    Apr 29, 2020 at 0:54
  • \$\begingroup\$ @petStorm Yeah, I guess it's different enough \$\endgroup\$ Apr 29, 2020 at 0:57
5
\$\begingroup\$

Draw a Peano Curve with Slashes

Given a positive integer N, draw the Nth iteration of the Peano Curve, using only slashes and backslashes (and spaces). The curve will be rotated at a 45 degree angle from its usual depiction. Here's an example for the first 3 iterations:

N = 1

 /\
/ /
 / /
 \/

N = 2

       /\
      / /
     / / /\
    /  \/ /
   / /\  / /\
   \/ /  \/ /
 /\  / /\  / /\
/ / / / / / / /
 / / / / / / / /
 \/ /  \/ /  \/
   / /\  / /\
   \/ /  \/ /
     / /\  /
     \/ / /
       / /
       \/

N = 3

                         /\
                        / /
                       / / /\
                      /  \/ /
                     / /\  / /\
                     \/ /  \/ /
                   /\  / /\  / /\
                  / / / / / / / /
                 / / / / / / / / /\
                /  \/ /  \/ /  \/ /
               / /\  / /\  / /\  / /\
               \/ /  \/ /  \/ /  \/ /
             /\  / /\  / /\  / /\  / /\
            / / / / /  \/ / / / / / / /
           / / / / / /\  / / / / / / / /\
          /  \/ /  \/ /  \/ /  \/ /  \/ /
         / /\  / /\  / /\  / /\  / /\  / /\
         \/ /  \/ /  \/ /  \/ /  \/ /  \/ /
       /\  / /\  / /\  / /\  / /\  / /\  / /\
      / /  \/ / / / / / / /  \/ / / / / / / / 
     / / /\  / / / / / / / /\  / / / / / / / /\
    /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /
   / /\  / /\  / /\  / /\  / /\  / /\  / /\  / /\
   \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /
 /\  / /\  / /\  / /\  / /\  / /\  / /\  / /\  / /\
/ / / / / / / / / / / / / / / / / / / / / / / / / /
 / / / / / / / / / / / / / / / / / / / / / / / / / /
 \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/
   / /\  / /\  / /\  / /\  / /\  / /\  / /\  / /\
   \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/ /
     / /\  / /\  / /\  / /\  / /\  / /\  / /\  /
     \/ / / / / / / /  \/ / / / / / / /  \/ / /
       / / / / / / / /\  / / / / / / / /\  / / 
       \/ /  \/ /  \/ /  \/ /  \/ /  \/ /  \/  
         / /\  / /\  / /\  / /\  / /\  / /\    
         \/ /  \/ /  \/ /  \/ /  \/ /  \/ /    
           / /\  / /\  / /\  / /\  / /\  /     
           \/ / / / / / / /  \/ / / / / /      
             / / / / / / / /\  / / / / /       
             \/ /  \/ /  \/ /  \/ /  \/        
               / /\  / /\  / /\  / /\          
               \/ /  \/ /  \/ /  \/ /         
                 / /\  / /\  / /\  /
                 \/ / / / / / / / /
                   / / / / / / / /
                   \/ /  \/ /  \/
                     / /\  / /\
                     \/ /  \/ /
                       / /\  /
                       \/ / /
                         / /
                         \/

You may optionally mirror this horizontally, vertically, or both if you choose. Leading spaces are clearly required for this. Trailing spaces are optional. This is code-golf, so the shortest code wins.

\$\endgroup\$
4
  • \$\begingroup\$ Is this what you were looking for? It seems like a direct duplicate. \$\endgroup\$ May 22, 2020 at 5:14
  • \$\begingroup\$ @dingledooper Ah, crud. I did a search and everything and that didn't come up. Maybe because it's too old or something. Oh well - should I just delete this then? Could switch it to the Peano or Gosper Curve, but I don't know if that would be appreciably different. \$\endgroup\$ May 22, 2020 at 13:12
  • \$\begingroup\$ The Gosper curve is a duplicate of codegolf.stackexchange.com/questions/50521/…. The Peano curve doesn't seem to be a duplicate, but I'm not sure whether it's a good idea. \$\endgroup\$ May 22, 2020 at 13:51
  • \$\begingroup\$ @mypronounismonicareinstate I changed it to the Peano Curve, might still be interesting to do. \$\endgroup\$ May 22, 2020 at 14:49
5
\$\begingroup\$

Score a 1 player game of Carcassonne

\$\endgroup\$
9
  • \$\begingroup\$ @dingledooper I'm not sure I understand? \$\endgroup\$ Jun 8, 2020 at 21:35
  • \$\begingroup\$ What I mean is, there are some tiles with roads going in more than one direction, so your scoring method seems to suggest that the same tile can be scored more than once. This is different than the official rules, which state that every tile may only be scored once. \$\endgroup\$ Jun 8, 2020 at 21:53
  • \$\begingroup\$ @dingledooper The rules state, when referring to scoring a road, "each tile of that road grants you 1 point" (emphasis mine). To me, that implies that a tile containing sections of multiple roads can be scored for each of those roads \$\endgroup\$ Jun 8, 2020 at 21:59
  • \$\begingroup\$ Ok, thanks for clearing that up for me. The only reason I asked was because it contrasted from the way I played Carcassonne (or how it is normally played). \$\endgroup\$ Jun 8, 2020 at 22:05
  • \$\begingroup\$ The scoring for incomplete road seems to have at least one incorrect word. Also, how are monasteries represented in your input format? \$\endgroup\$
    – Neil
    Jun 9, 2020 at 9:49
  • \$\begingroup\$ Or indeed villages. \$\endgroup\$
    – Neil
    Jun 9, 2020 at 9:49
  • \$\begingroup\$ @Neil Yes, it does, thanks for spotting that. The monastery tiles are [0, 0, 0, 0, 0] and [0, 0, 1, 0, 0]. As no other tile can be described by these two, I didn’t think it would be necessary to add an additional value representing a monastery. It’s similar with villages; each of the tiles with a village on is unique without having to specify that it has a village on it. For instance, the tile [1, 2, 1, 1, 1] (a rotation of [2, 1, 1, 1, 1]) is guaranteed to have a village on it, so another value is unnecessary. \$\endgroup\$ Jun 9, 2020 at 14:38
  • \$\begingroup\$ Ah, so a tile with at least 3 roads always has a village, and a tile with no features apart from an optional single road always has a monastery? \$\endgroup\$
    – Neil
    Jun 9, 2020 at 16:26
  • \$\begingroup\$ @Neil Yes exactly \$\endgroup\$ Jun 9, 2020 at 16:29
5
\$\begingroup\$

Posted: Scoring Quantum Tic-Tac-Toe

\$\endgroup\$
10
  • \$\begingroup\$ Do cyclic entanglement always have len=3? \$\endgroup\$
    – l4m2
    Jun 17, 2020 at 22:26
  • \$\begingroup\$ @l4m2 A cyclic entanglement can have any length provided it fits on the board. For instance, in the case DE AB DE 1 AH CF CH CG BC 2, there is a loop of length 4 across A, B, C and H. I will make a note of this in the challenge. \$\endgroup\$
    – golf69
    Jun 17, 2020 at 23:49
  • \$\begingroup\$ @l4m2 In that same case, there is also a loop of length 2: DE .. DE \$\endgroup\$
    – golf69
    Jun 17, 2020 at 23:53
  • \$\begingroup\$ I don't think the description directly states that the other player chooses the state in all cases \$\endgroup\$ Jun 18, 2020 at 3:41
  • \$\begingroup\$ Can describing what state was chosen be done in other ways? For example, writing the number of the mark that fills the cell of the last quantum mark placed might be useful instead of the lowest cell alphabetically. \$\endgroup\$ Jun 18, 2020 at 3:44
  • \$\begingroup\$ @fireflame241 Yes, you can choose to describe the state chosen in whatever way is convenient (I added your example to the "rules" section). And thanks for pointing that out about who chooses the state, it's clear now I hope \$\endgroup\$
    – golf69
    Jun 18, 2020 at 4:17
  • \$\begingroup\$ In your illustration, does the position of the quantum marks in a single cell (e.g. in your second picture, the center cell has three marks arranged in a J shape) matter? \$\endgroup\$
    – Trebor
    Jun 18, 2020 at 7:19
  • \$\begingroup\$ @Trebor It does not, noted \$\endgroup\$
    – golf69
    Jun 18, 2020 at 8:00
  • \$\begingroup\$ Is it possible input go on there after result comes? \$\endgroup\$
    – l4m2
    Jun 19, 2020 at 4:33
  • \$\begingroup\$ @l4m2 No: "A game continues until at least one tic-tac-toe is formed or until the board is filled with classical marks." I will add that no more moves can be done after this and that multiple tic-tac-toes can only be formed simultaneously \$\endgroup\$
    – golf69
    Jun 19, 2020 at 5:01
5
\$\begingroup\$

Build an alphabetised polyglot

\$\endgroup\$
5
\$\begingroup\$

My smart phone

Posted here: My smartphone's phonebook

\$\endgroup\$
11
  • 1
    \$\begingroup\$ I like this idea. Just to make sure I've understood the challenge correctly, given a phone number, are we to find all possible strings that match it within a database of strings? \$\endgroup\$
    – lyxal
    Jul 24, 2020 at 11:45
  • \$\begingroup\$ Not quite. Given a database/list of strings, split these by space into words. Return all database entries that contain a word that matches the number. \$\endgroup\$ Jul 24, 2020 at 13:20
  • \$\begingroup\$ Duplicate? \$\endgroup\$ Jul 24, 2020 at 19:27
  • 1
    \$\begingroup\$ This question only asks return entries consisting of one word, while this asks to check for possibly multiple words per entry and then to return the complete entry. Also, this quesition had unusual and harsh restrictions. This aims to be much more simpler than that, making the puzzle more attractive. While the first reason may be splitting hairs, the second one, combined with the puzzle being ~6 yrs old, is a good reason to post this puzzle, imo. \$\endgroup\$ Jul 26, 2020 at 9:23
  • \$\begingroup\$ Add my name in! \$\endgroup\$
    – null
    Aug 2, 2020 at 13:44
  • 1
    \$\begingroup\$ 'You may only take input in some form of list type, not a string.' Rigid I/O requirements are generally frowned upon. \$\endgroup\$
    – Dingus
    Aug 5, 2020 at 1:34
  • \$\begingroup\$ True, no idea why I insisted on that. I'd rather not have this challenge killed because of a probably useless constraint. \$\endgroup\$ Aug 5, 2020 at 12:51
  • 1
    \$\begingroup\$ You've probably thought of this, but you could get more names from Users. (I'm chuffed to have already made the cut, by the way!) Is there a mistake in the 34 test case - wouldn't HighlyRadioactive appear under 44? \$\endgroup\$
    – Dingus
    Aug 5, 2020 at 13:26
  • \$\begingroup\$ whoops... fixed. I'll add some more people from Users when posting, for the test cases I've just listed some people I see a lot off the top of my head. Also, if you gave some feedback, there's no reason not to put you in there. \$\endgroup\$ Aug 6, 2020 at 6:22
  • \$\begingroup\$ Why is fireflame241 there twice? \$\endgroup\$ Aug 14, 2020 at 15:14
  • \$\begingroup\$ Third-Party 'Chef' is now called petStorm - update. \$\endgroup\$
    – null
    Aug 20, 2020 at 8:38
5
\$\begingroup\$

Implement the random Fibonacci sequence

\$\endgroup\$
15
  • \$\begingroup\$ Is -3 a valid output for f5? \$\endgroup\$
    – tsh
    Aug 31, 2020 at 6:27
  • \$\begingroup\$ But it is possible that f3 = 2. It is also possible that f4 = -1. \$\endgroup\$
    – tsh
    Sep 1, 2020 at 1:52
  • \$\begingroup\$ @tsh It is possible that f3 = 2 and it is possible that f4 = -1, but the two cannot be satisfied at once. So the challenge requires to record the previous results, I think (and therefore some short approaches like naive recursion can't be used). \$\endgroup\$
    – Bubbler
    Sep 1, 2020 at 2:45
  • 1
    \$\begingroup\$ It would be good to include the correct distributions of the first few entries, like f_3 to f_6, for testing purposes. \$\endgroup\$
    – Zgarb
    Sep 1, 2020 at 7:46
  • \$\begingroup\$ @cairdcoinheringaahing f3 = f2 + f1 = 1 + 1 = 2; f4 = f3 - f2 = (f2 - f1) - f2 = (1 - 1) - 1 = -1; f5 = f4 - f3 = -1 - 2 = -3; If this is not what you want, you may need to update your description to avoid ambiguous. \$\endgroup\$
    – tsh
    Sep 2, 2020 at 1:45
  • \$\begingroup\$ @tsh Took me a while, but I think I understand what you're getting at. Does my latest edit address that? \$\endgroup\$ Sep 8, 2020 at 22:18
  • \$\begingroup\$ @Zgarb Not the best when it comes to distributions, but I've added in a list of possible values for n = 1 ... 6 \$\endgroup\$ Sep 8, 2020 at 22:18
  • \$\begingroup\$ I was going to edit in the distributions, but I don't believe your last case is correct. I don't think there is a way to reach 6 or -3. I decided to edit it in anyway since I wrote it on a scrap of paper, but of course feel free to change it if I am wrong. \$\endgroup\$ Sep 9, 2020 at 21:14
  • \$\begingroup\$ If given n we just output f_n, this voids the requirement that the sequence should remember previous values, doesn't it? \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 16:14
  • \$\begingroup\$ @LuisMendo No, the requirement that the sequence "remembers" previous values is means that tsh's comment above would be an invalid way to construct the sequence. Because \$f_n\$ is constructed from previous terms, those terms cannot change partway through the construction of the sequence. For example, while constructing \$f_6\$, you'd have to first get the values for \$f_{1,\dots5}\$. Then, when constructing \$f_7\$, the values of \$f_{1,\dots5}\$ would be the same as when getting \$f_6\$, whether they were outputted or not. \$\endgroup\$ Sep 12, 2020 at 16:18
  • \$\begingroup\$ Ah, I see, So, "remember" means that in the construction of a given f7, every occurrence of f1 etc should have the same value. \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 16:44
  • \$\begingroup\$ @LuisMendo Yes exactly. If you have a better wording, I'd love to hear it, I'm not too happy with "remember" \$\endgroup\$ Sep 12, 2020 at 17:18
  • \$\begingroup\$ @cairdcoinheringaahing Here's a suggestion: Each random realization of the sequence must use consistent values. For example, if [...] \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 20:22
  • \$\begingroup\$ Also, when you say is chosen at random, you probably mean is chosen at random independently of previous choices? This prevents the code from randomly choosing a sign and using it for all terms, for example \$\endgroup\$
    – Luis Mendo
    Sep 12, 2020 at 20:23
  • 1
    \$\begingroup\$ @LuisMendo That wording is nice, thanks! And yes, each choice should be independent, I'll edit that it \$\endgroup\$ Sep 12, 2020 at 20:59
5
\$\begingroup\$

Minimise a bijection \$\mathbb{N}^n\to\mathbb{N}\$

\$\endgroup\$
9
  • \$\begingroup\$ Seems very possible. You can iterate the cantor pairing function \$\pi(\pi(\pi(a,b),c)\ldots)\$ \$\endgroup\$
    – Sisyphus
    Oct 17, 2020 at 2:08
  • \$\begingroup\$ @Sisyphus, yes, but can you iterate it \$n\$ times within \$n\$ bytes? \$\endgroup\$ Oct 17, 2020 at 11:58
  • \$\begingroup\$ Also, I like this scoring idea but I fear that the abstractness of the task will scare away potential golfers. Maybe it would be better to choose a simpler task that has n as a parameter. \$\endgroup\$
    – Zgarb
    Oct 18, 2020 at 19:42
  • \$\begingroup\$ @Zgarb While I do agree that, because it's much harder with the self-referential part, a simpler challenge would probably do better (votes/answers wise), but I've got no issue with this going unanswered, and I think as is, it'll draw much more impressive answers with a more discriminating choice of bijections. \$\endgroup\$ Oct 18, 2020 at 19:44
  • \$\begingroup\$ Finally, you're missing the condition that every natural number must occur as an output. \$\endgroup\$
    – Zgarb
    Oct 18, 2020 at 19:45
  • \$\begingroup\$ Plus, because of the self-referential part, I think that this doesn't close the door on any future challenges that allow you to choose your own \$n\$, or take \$n\$ as a parameter, so I'm happy with this scoring criteria. Also, thanks for noticing that, edited in. \$\endgroup\$ Oct 18, 2020 at 19:46
  • \$\begingroup\$ I don't really see the point of the n-is-length idea. It seems like you just have to write code that works for any n, then plug in n equal to the length of the code (accounting for the replacement). Only perhaps an ultra-golfy language might be able to do something like n=2 in 2 bytes rather than writing a general solution. \$\endgroup\$
    – xnor
    Oct 18, 2020 at 21:41
  • \$\begingroup\$ @xnor IMO, it adds an extra level of complexity/difficulty to the challenge, in that you have to modify the actual code as you modify code length. Also, I don't think the generic "take \$n\$ as a parameter" version is particularly interesting, whereas requiring answers to link \$n\$ and their code is \$\endgroup\$ Oct 18, 2020 at 22:03
  • \$\begingroup\$ @cairdcoinheringaahing Can you give an example of an interesting thing a program could do in linking its code length? I'm really not seeing it. The only extremely minor thing I could see is that if you have, say, a 76 byte program that works excepts it has a spot you need to put the number in, you need to put in 78 to account for the length of the code and number. \$\endgroup\$
    – xnor
    Oct 18, 2020 at 22:10
5
\$\begingroup\$

Quickly! Group together!

\$\endgroup\$
4
  • \$\begingroup\$ This seems like fun! I have one concern, though. The first is that keeping track of all of the restrictions that have already been used seems like an unnecessary headache. Testing if a language has been used is fairly easy using the SE search (you might want to add in some premade links to make it easier for people to do) and I think that will help the variety enough. This seems like it would become a headache faster than it is worth, even if you did something like updating the challenge each day. \$\endgroup\$ Nov 13, 2020 at 2:59
  • \$\begingroup\$ @FryAmTheEggman Yeah, that's my main concern is keeping track of everything. Maybe adding a Stack Snippet to the challenge body that extracts previously used restrictions could alleviate that (similar to what we did with my OEIS answer chaining for used sequences)? I'm hesitant to remove the rule about not reusing restrictions, because it could just lead to the challenge continuing ad infinitum with a couple of basic, repeated restrictions \$\endgroup\$ Nov 13, 2020 at 13:50
  • \$\begingroup\$ Trivial restrictions are so numerous that I don't believe this rule is doing anything relevant to end the challenge faster. I'd recommend dropping it and thinking about some other way to limit solutions if you really want that. \$\endgroup\$ Nov 13, 2020 at 16:46
  • \$\begingroup\$ I agree with @FryAmTheEggman about the restrictions. Your rule that languages can't be used on different days should be enough to ensure that the challenge ends eventually. \$\endgroup\$ Nov 22, 2020 at 23:47
5
\$\begingroup\$

Is it a vampire number?

\$\endgroup\$
4
  • \$\begingroup\$ The old challenge certainly suffers from strict I/O, but I don't have a strong opinion as to whether it should be closed in favour of this one. If you do go ahead, I suggest clarifying that \$x\$ and \$y\$ must both have the same number of digits and only one of them may end with 0. \$\endgroup\$
    – Dingus
    Jan 20, 2021 at 22:10
  • \$\begingroup\$ @Dingus "strict I/O" is a bit of an understatement. I have a Jelly answer to this and the old one. This is 10 bytes, the only one is 45 bytes, and the difference in length comes entirely from having to format the output to meet the rules, which no-one likes doing. Good spot on the restrictions on \$x\$ and \$y\$ \$\endgroup\$ Jan 21, 2021 at 9:19
  • \$\begingroup\$ I definitely see your point. I'm not opposed to the repost, in case I wasn't clear. \$\endgroup\$
    – Dingus
    Jan 21, 2021 at 21:42
  • \$\begingroup\$ I vote for the repost \$\endgroup\$
    – anotherOne
    Jan 22, 2021 at 20:09
5
\$\begingroup\$

I decide to change the statement a little, so people who don't know the language can easily understand the challenge. (apparently there are many)


Background:

  • I'm thinking about scraping some BF programs on this site for the fastest-code (or approximation) version of the other challenge, and I figure out that I need to have this, and I post it here as a code-golf challenge since it's somewhat interesting (and also pretty easy).
  • It's possible to force programs to check if there are any extra characters too; however it might make the problem harder (only allow printable ASCII? Some scraped data might have non-ASCII characters, so it isn't really practical. Any Unicode characters as input? Most esoteric languages can't handle that.)

Does this BF program have a simple memory layout?

Given a string consisting of only the characters +-[]<>., check if:

  • All pairs of [] are matching (balanced), and
  • There's an equal number of < and > between every matching pair of [].

Background: the inputs that this program output true are exactly the valid inputs for the related challenge BF memory layout optimizer.

Reference implementation in Python 3.

Example input/output

Output true:

,>>,
,<++[->>+<<]
+<><>+
,[.,]
>.<

Output false:

,[>,]
+[>>>->-[>->----<<<]>>]>.---.>+..+++.>>.<.>>---.<<<.+++.------.<-.>>+.
].[

Undefined behavior: (your program can do anything when given those as input)

((((()()()()()){}){}){}())
$\="=".hex.$/
\!$/'?))='%<\..>
\$\endgroup\$
3
  • \$\begingroup\$ can you please make the rules a list, some of us are bad at reading. \$\endgroup\$
    – Alex bries
    Feb 4, 2021 at 9:30
  • \$\begingroup\$ @Alexbries But there are only two of them... \$\endgroup\$
    – DELETE_ME
    Feb 4, 2021 at 9:46
  • 1
    \$\begingroup\$ I was worried for a bit this would delve into Rice's Theorem territory (the similar question "does this BF program have bounded memory consumption?" would). Seems plenty simple though. \$\endgroup\$
    – Beefster
    Feb 10, 2021 at 23:18
5
\$\begingroup\$

KoTH: Hunter-Gatherer Society

, ,

In this challenge, the goal is to write a bot (Javascript function) which survives for as long as possible with its tribe. The bots are placed on an island, with the ability to hunt, gather, farm, and build. Tribes can fight, and the last alive wins.

This challenge is complicated, and it's designed to be that way. I'd recommend starting out with bots that specialize in a particular type of strategy, like gathering berries or fighting. To keep this post from being longer than it already is, technical details will be included in the links labeled More at the end of each section. (Meta: These links don't go anywhere yet)

Overview

Bots have hit points and hunger. In order to survive, bots need to eat. There are various foods, such as berries from berry bushes, bread from farming, and meat from hunting. Materials like sticks, rocks, logs, and ores can be found around the island, and used to make tools and buildings.

The island has grasslands, forests, and rivers. Rabbits and elk can be hunted for meat and hide, with sticks, rocks, or spears. Meat can be cooked over a campfire. Tribes can build walls to protect their farms and bases, and fight to defend them with weapons and armor. Bots can talk to their tribe members, and trade for rare materials.

Hit Points, Hunger, and Turns

All bots have a number of hit points, and a number of hunger points. Bots start with 7.5 hit points, out of a maximum of 10. When they reach 0 or below, they die. Various actions take hunger. Bots start with 75, out of a maximum of 100, and when they drop below 0 hunger points they instead lose 10% of the hunger taken in hit points.

Games consist of a number of turns. During each turn, all bots can perform actions including moving, eating, harvesting, and fighting. Each action takes a certain amount of hunger, and every action performed in the same turn after the first one doubles the hunger taken.

More: Turns

Terrain

The world consists of a square grid, with a radius determined by floor(25 * sqrt(bot_count)) + 25. The center of the grid will always be [0, 0], with coordinated ranging from [-radius, -radius] to [radius, radius]. Positions will always be specified in absolute coordinates as an array [x, y], and most actions that take a position argument will require the bot to be adjacent to that position unless otherwise specified.

This land is divided into four biomes:

  • Grassland
  • Forest
  • River
  • Ocean

The outer ring of 25 grid squares will be ocean. This consists of a beach closer to the center, with water continuing to the boundary of the world. Rivers will generate similarly, usually with a width of 5-10, with a thin beach on each side.

Each naturally generated terrain square can be one of the following:

  • Plain
  • Bush
  • Berry bush
  • Tree
  • Stone
  • Copper ore
  • Iron ore
  • Sand
  • Water

Grasslands are mostly plain, with some stones and bushes. Forests are more interesting, with many trees and some stones, bushes, and berry bushes.

More: Terrain

Movement

Bots can move in any of four directions: north(), east(), south(), or west(). Only some terrain can be walked into:

  • Plain
  • Sand
  • Farmland
  • Bush (+1)
  • Berry bush (+1)
  • Water (+2)

It typically takes 1 hunger to move. However, moving into certain terrain (marked with +1 or +2) can take extra hunger. An addition hunger point is taken for every 10 items the bot is holding, rounded down. Multiple bots can occupy the same position.

Food

There are four foods, which restore different amounts of hunger:

  • Berries: 10
  • Meat: 15
  • Bread: 25
  • Cooked meat: 40

Foods also restore 10% of their hunger restoration in hit points.

Berries can be collected from berry bushes, by returning harvest() when adjacent to (or standing in) a berry bush. Meat is obtained by hunting, bread is crafted with grain, and cooked meat requires a campfire.

Grain can be initially collected by returning harvest() when adjacent to (or standing in) plain land. It can also be collected from farming. Bread can be crafted by returning craft(Item.BREAD) while holding 1 grain and 1 rock. The rock will not be consumed.

More: Food, Harvesting

Resources

Many types of terrain can be broken by returning break(position), turning into plain land and giving items:

  • Bush: Stick × 1
  • Berry bush: Berries × 1
  • Tree: Log × 2
  • Stone: Stone × 1
  • Copper ore: Copper ore × 1
  • Iron ore: Iron ore × 1

Trees require an axe to break. All four will reappear after a number of turns if the land remains plain.

A stone axe can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_AXE), and will break after 10 uses.

More: Breaking, Crafting

Farming

A stone shovel can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_SHOVEL). A shovel can be used to turn plain land into farmland, and will break after 20 uses. This is done by returning shovel(position).

Grain can be planted on farmland by returning plant(position). It will take around 100 to 200 turns to grow, although the amount of time is much shorter within 20 squares of water. Grain starts as Growth.NOT_GROWN, and cannot be harvested (only broken). It then becomes Growth.GROWING after about 70% of the total time, and will give one grain when broken or harvested. Finally, the last stage is Growth.GROWN, where two to four wheat are given from harvesting.

More: Farming

Hunting

A stone spear can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_SPEAR). A spear can be used to hunt, as well as a stick or stone. Bots can attack at a position by returning attack(position) (hunt(position) and fight(position) are aliases). Movement happens before attacking, so simply attacking an animal's current position may not work. If attacking would hit multiple targets, damage is distributed between them evenly.

Sticks and stones have a range of 1, with sticks dealing 0.35 hit points, and stones dealing 0.75. Spears deal one hit point, with a maximum range of 2. A spear breaks after 10 successful hits. Attacking takes 10 hunger, whether or not any target is successfully hit.

There are two types of animals: rabbits and elk. Rabbits have 1 hit point, and elk have 4. Rabbits will move every 1 to 2 turns, avoiding bots if they are very close. Elk will move every 2 to 4 turns, and will always move away from attackers for 2 to 4 turns after being attacked. Rabbits will give the last bot to hit them 1 meat, and have a 25% chance of giving 1 hide to the second to last player to hit them. Elk are similar, giving 1 meat and 1 hide to the last bot to hit them, and 1 meat to the bot that hit them the 2nd to last time.

More: Hunting

Tribes

All bots will be part of a tribe. Tribes are determined by the creator of the bot, can contain any number of bots from any number of writers. Bots in the same tribe will be able to recognize each other, while bots outside their tribe will only have their tribe name known. Tribe members cannot attack each other.

If a tribe member is next to another one, they can give an item with give(name, item), or transfer any JSON-serializable data with talk(name, data).

Armor can be crafted from 2 hide with craft(Item.ARMOR). When a bot is holding armor, it can take up to 10 hit points before breaking. Bots fight with other bots in the same way they hunt animals. When a bot is killed, its items are distributed among the bots that attacked it recently according to the damage done.

More: Tribes, Fighting

Building

Bots can build walls and campfires, by returning build(build, position), where build is one of Terrain.WOOD_WALL, Terrain.STONE_WALL, Terrain.CRATE, or Terrain.CAMPFIRE. Wood walls require 2 logs, and take 10 hits with an axe to break, giving the bot that breaks it one log. Stone walls require 4 stones, and take 75 hits with an axe to break, giving the bot that breaks it one stone.

Crates require 1 log and 1 bronze, and can store items. If you're adjacent to a crate, you can store items in it with store(position, items), and take an item with take(position, items). Crates can store up to 40 items. The contents of crates are visible to any bot.

Campfires require 1 stone, and 2 sticks, and can be used to cook meat. Campfires can be given fuel using fuel(position, item), accepting sticks, logs, and charcoal. Bots can cook meat or logs (which turn into cooked meat and charcoal, respectively) using cook(Item.MEAT) or cook(Item.LOG), if adjacent to a campfire. Cooking meat uses 3 fuel, and cooking logs uses 5. A stick provides 1 fuel, a log provides 5, and charcoal provides 15.

A campfire can be broken with an axe, and will give the bot that breaks it all of the unused fuel it holds. Partially consumed logs or charcoal will not be given.

More: Building, Cooking

Upgrading

Copper ore and iron ore can be cooked into bronze and iron in a campfire, requiring 10 and 15 fuel respectively. Bronze and iron can be used to craft stronger axes, shovels, and spears, by replacing the stone in the recipe with the corresponding item.

For axes and shovels, the material affects the durability:

  • Stone axe: 10
  • Bronze axe: 15
  • Iron axe: 25

All shovels have twice the durability of a similarly strong axe. Spears are different, with all tiers having 10 durability. Instead, the number of hit points dealt is upgraded:

  • Stone spear: 1.0
  • Bronze spear: 1.5
  • Iron spear: 2.5

Because these items are so rare, trading might be a good way for a tribe to advance. By returning offer(sell, buy), any bot can offer a number of items they have (sell) for a number of items they want to have (buy). All bots will receive an array of offers made on the last turn, and can accept one with accept(offer), where offer is an offer ID.

The sell array should contain IDs of items the bot is holding, while buy should be an array of objects. All objects should have an item property with the Item wanted, and an optional durability property can specify a minimum durability acceptable. If no minimum durability is included, only undamaged items will be accepted.

More: Trading

Bots

Many arguments and functions involve enums including Terrain and Item. Here is a reference:

  • Terrain: PLAIN, BUSH, TREE, STONE, COPPER_ORE, IRON_ORE, FARMLAND, SAND, WATER, WOOD_WALL, STONE_WALL, CAMPFIRE
  • Item: STICK, BERRIES, LOG, STONE, COPPER_ORE, IRON_ORE, CHARCOAL, BRONZE, IRON, MEAT, COOKED_MEAT, GRAIN, BREAD, HIDE, ARMOR, STONE_AXE, BRONZE_AXE, IRON_AXE, STONE_SHOVEL, BRONZE_SHOVEL, IRON_SHOVEL, STONE_SPEAR, BRONZE_SPEAR, IRON_SPEAR
  • Growth: EMPTY, NOT_GROWN, GROWING, GROWN
  • Animal: RABBIT, ELK

All bots should be Javascript functions, which take four arguments:

  • grid: A 15 by 15 grid centered around the bot, with all items being objects:
    • terrain: A type of Terrain
    • details: An object, with a has_berries property for Terrain.BUSH, a growth property for farmland (Growth.EMPTY if no grain is planted), a hit_points property for walls (starts as 10 for wood or 75 for stone), and a fuels property for campfires (array of Items.STICK, Items.LOG, and Items.CHARCOAL, does not include partially burned)
    • bots: An array of bots, with all being objects:
      • tribe: A string containing a tribe name
      • name: A string containing a bot name, if the bot is in the same tribe
    • animals: An array of animals, with all being one of Animal.RABBIT or Animal.ELK
  • bot: An object with information about the bot:
    • hit_points: Hit points
    • hunger: Hunger
    • position: Position as [x, y]
    • items: An array of items held, with all items being objects:
      • id: A unique ID for this item
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the remaining uses (or hit points) until broken
  • offers: An array of offers from other bots on the last turn:
    • id: An ID unique to the offer
    • sell: An array of the items the seller is offering:
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the remaining uses (or hit points) until broken
    • buy: An array of items the seller wants:
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the minimum durability acceptable
  • talking: An array of data sent from other bots on the last turn:
    • name: The name of the sending bot
    • data: The data sent by the bot
  • storage: An object that can be used for storage between turns

Meta

(Note that none of the links to More work yet)

  • Is this clear enough as it is, without the technical details?
  • Is there too much information, or is it too hard to read?
  • Do you think there will be strategy and clever bot design?
  • Would you compete in this challenge? Why not?

New features

Things I recently added:

  • Trading between tribes
  • Communication within tribes
  • Bronze and iron, and better tools
  • Crates to store items
\$\endgroup\$
8
  • \$\begingroup\$ When you say "Bots start with 75, out of a maximum of 100, and when they drop below 0 hunger points they instead lose 10% of the hunger taken in hit points." Did you mean: "Bots start with 75 hitpoints, out of a maximum of 100, and when they drop below 0 hit points they instead lose 10% of the hunger taken in hit points."? \$\endgroup\$ Mar 9, 2021 at 4:58
  • \$\begingroup\$ @DanielOnMSE The reverse, mostly. Bots start with 7.5/10 hit points, and 75/100 hunger. When a bot drops below 0 hunger, additional hunger is taken from the bot's hit points instead (but scaled by 10%) \$\endgroup\$ Mar 9, 2021 at 5:19
  • \$\begingroup\$ Ahh okay. I think this contradicts "Bots start with 7.5 hunger, out of a maximum of 10. When they reach 0 or below, they die" Unless hitpoints/hungers still mean something when dead? Nice idea btw. I've upvoted. I'll continue to trawl through it and see if I can find any errors. I think I get what you are trying to say with the hitpoints/hunger but I think you may have accidentally swapped the two in some places? \$\endgroup\$ Mar 9, 2021 at 5:28
  • \$\begingroup\$ @DanielOnMSE Ah, I see what you mean. I'll fix that. \$\endgroup\$ Mar 9, 2021 at 5:44
  • \$\begingroup\$ Just food for thought. Might make the challenge more approachable if you wrote a script that created the world state and takes input/gives output every turn to the bots? Or is part of this challenge making the "game" itself? Perhaps you've already considered this and made something. Whether or not this is implemented will determine the complexity of this, imo. Like if you could create something everyone involved could use to test their bot? Also give it fixed input and output formats? \$\endgroup\$ Mar 9, 2021 at 5:53
  • 2
    \$\begingroup\$ @DanielOnMSE Usually that's part of making a KoTH, yeah. There's a controller program (usually written by the author before posting) that manages all of the bots, sets up the games, determines the winner, etc. \$\endgroup\$ Mar 9, 2021 at 13:21
  • \$\begingroup\$ This challenge seems very interesting but even more complex to me... but I'd give it a try. However, it would need many participating bots to utilize all of its features and make it fun to play. Technical note: break won't work as a function name (it's reserved) unless it's an object property. \$\endgroup\$
    – FZs
    May 18, 2021 at 15:38
  • 1
    \$\begingroup\$ @FZs Part of my goal when designing this KotH was specifically for it to be very complex; I'm hoping bots will be sort of forced to specialize. Thanks for noticing the break thing, I guess I'll rename that to destroy or mine \$\endgroup\$ May 18, 2021 at 15:40
5
\$\begingroup\$

Liars and Guessers

\$\endgroup\$
8
  • \$\begingroup\$ this looks like a very good challenge. I'd go with JS for the language. \$\endgroup\$ Feb 28, 2021 at 14:16
  • 1
    \$\begingroup\$ Be careful. If the minimax algorithm is not too hard, then people can just implement it and effectively block all the other answers. \$\endgroup\$
    – DELETE_ME
    Feb 28, 2021 at 14:55
  • \$\begingroup\$ Isn't JavaScript very good for sandboxing? The browser is the sandbox. / Besides, you can ask people to explain suspicious code, obviously... \$\endgroup\$
    – DELETE_ME
    Feb 28, 2021 at 14:56
  • \$\begingroup\$ @user202729 Re sandboxing I was less worried about safety than clever people inspecting the program's memory/whatever. But I guess I can just forbid it. \$\endgroup\$
    – Artemis
    Feb 28, 2021 at 14:58
  • \$\begingroup\$ @user202729 Re minimax, I was worried that it might be too trivial to come up with a perfect solution. I'll look into it. \$\endgroup\$
    – Artemis
    Feb 28, 2021 at 15:00
  • \$\begingroup\$ IMO, either Python or JS would be suitable to this question. You can chose any of them and it should work fine. As this question is asking about strategy of guessing instead of golfing in specified languages. People try to answer this question are not required to know very details of the language used. \$\endgroup\$
    – tsh
    Mar 9, 2021 at 6:00
  • \$\begingroup\$ To my understanding, guesser_score = sum(times_guessed for number in ([0..255] repeat 10 times) for each liar), lower is better. (10 times repeating is required since most submission would relay on some random behaviors.) liar_score is defined similar but higher is better. Use liar_score - guesser_score or liar_score / guesser_score (I would prefer the div one) to get score for some answer. \$\endgroup\$
    – tsh
    Mar 9, 2021 at 6:16
  • \$\begingroup\$ Wrote a Python implementation. It treats liars and guessers as separate submissions. \$\endgroup\$
    – Artemis
    Mar 9, 2021 at 15:35
5
\$\begingroup\$

Self-Replicating Numbers

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Nice challenge, but I feel it would be more interesting if it took two inputs, m and n, and outputted either the first m n-order numbers or the mth n-order number. \$\endgroup\$
    – user
    Mar 5, 2021 at 15:29
  • \$\begingroup\$ @user I do like that; my original concept for the challenge was similar (outputting the first n distinct orders). I think your concept is more interesting, but I do worry about the run time - I'll run some tests and see if there are enough reasonable test cases. Thanks for the feedback! \$\endgroup\$ Mar 5, 2021 at 15:34
  • \$\begingroup\$ For the formatting thing, see math.meta.stackexchange.com/questions/5020/… -- replace $ with \$. \$\endgroup\$
    – DELETE_ME
    Mar 6, 2021 at 10:54
  • \$\begingroup\$ Add "exactly" (appear [...] exactly \$n\$ times [...]) in the definition too, if that's what you mean. \$\endgroup\$
    – DELETE_ME
    Mar 6, 2021 at 10:55
  • \$\begingroup\$ +1 nice challenge! I have no idea of how to verify that there are no 1st-order self-replicating numbers after 9. \$\endgroup\$
    – anotherOne
    Mar 7, 2021 at 12:55
  • 1
    \$\begingroup\$ @SheikYerbouti Thanks! Think of it this way; since you're checking all multiples of a number up to their square, every number from 10 and up will have the multiple of itself and ten checked - any number times ten is guaranteed to have the original number as a substring. Numbers from 100 and up will have the multiple of itself and 100 checked, and so on. \$\endgroup\$ Mar 7, 2021 at 14:42
  • \$\begingroup\$ Oh you are right! That's clever (or I am slow ahaha) \$\endgroup\$
    – anotherOne
    Mar 7, 2021 at 15:29
  • \$\begingroup\$ Allowing output of the infinite sequence of n-order numbers would be nice. \$\endgroup\$
    – Razetime
    Mar 9, 2021 at 14:44
  • \$\begingroup\$ @Razetime I wanted to make it a little more challenging by requiring both inputs - would it make sense to allow outputting the infinite sequence of numbers that are either m or n order, or is that too complicated? I want there to be reasons to choose either output option, if I choose to add more, and I fear that the infinite series of n-order will be the easier choice for a majority of languages. Let me know if I'm just overthinking it, and thanks for the feedback! \$\endgroup\$ Mar 9, 2021 at 16:02
  • \$\begingroup\$ @ZaelinGoodman many recent sequence challenges allow output in 3 main ways: nth number, first n numbers or an infinite sequence. It is up to you to choose what you think suits the challenge best. \$\endgroup\$
    – Razetime
    Mar 9, 2021 at 16:08
  • \$\begingroup\$ @Razetime Ohhh okay; I looked at a few other sequence challenges and pulled together a few options - I do think it rounded out the challenge a bit more, but now I'm not sure how better to format the test cases area to accommodate those additional output modes \$\endgroup\$ Mar 9, 2021 at 16:45
  • \$\begingroup\$ Minor things: can you change the wording and formatting of the "The CHallenge" section to make it more obvious that you need to do one of the things (see some existing sequence questions for more info)? Also can you clarify that you mean a substring in decimal? Can you clarify that "if the input is not valid" means "if no such number exists". Finally, what tags are you planning to use? code-golf sequence number ...? \$\endgroup\$
    – pxeger
    Mar 10, 2021 at 17:19
  • 1
    \$\begingroup\$ @pxeger Thanks, I have implemented all of your suggestions - let me know if you still feel any of those areas are lacking! \$\endgroup\$ Mar 10, 2021 at 18:41
5
\$\begingroup\$

Minimally destroy CGCC in Game of Life

\$\endgroup\$
8
  • \$\begingroup\$ Just to clarify, you get an integer \$n\$ as input and must kill all but \$n\$ cells from the initial state to produce the shortest lived automata? \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 17:44
  • \$\begingroup\$ Are there performance requirements? This problem is in EXPTIME. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 17:45
  • \$\begingroup\$ @Beefster No time requirements. And no, you decide how many cells you want to make alive (call that \$n\$) and which cells they are. You then run the game with those cells and the initial CGCC being alive until it reaches a point where all cells on the board are dead. Lowest \$n\$ wins. \$\endgroup\$ Mar 22, 2021 at 17:47
  • \$\begingroup\$ Oh, I get it. You're supposed to add live cells around the initial CGCC so that the board eventually anihillates. The way you framed the challenge is a little confusing. You make it seem like you're supposed to remove cells from the initial configuration. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 18:02
  • \$\begingroup\$ @Beefster I've edited the wording slightly, does it make more sense? \$\endgroup\$ Mar 22, 2021 at 18:05
  • \$\begingroup\$ The wording is clearer now, but the issue is that "However, if we change the initial state to the following, by changing 13 cells, then, after 31 iterations, the board is empty" is sort of misleading because it prepares the reader to remove cells when you then say "And this is your task." I think it would be less confusing if you gave an example where adding cells to an initial state causes the pattern to eventually annihilate. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 19:20
  • \$\begingroup\$ @Beefster The issue with that is that I don't actually have an example that fits the current rules :/ \$\endgroup\$ Mar 22, 2021 at 19:38
  • \$\begingroup\$ You don't necessarily need to create an example that fits the rules. You could instead give an example of a simpler pattern that, when a few additional cells are made live, leads to eventual annihilation. So the overall flow of the challenge description would be something like this: simple pattern, simple pattern + live cells --> annihilation, CGCC pattern creates still life + oscillators, description of the task and scoring. \$\endgroup\$
    – Beefster
    Mar 22, 2021 at 20:02
5
\$\begingroup\$

Posted

\$\endgroup\$
1
  • \$\begingroup\$ Instead of saying that "Output is undefined if n<1, or if A is shorter than n" just specify that this won't be the case. \$\endgroup\$
    – Adám
    Mar 24, 2021 at 13:54
5
\$\begingroup\$

Two Diehards Make a Glider


POSTED

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Is the WIP for the title or the challenge? The challenge looks mostly ok, but I'd be worried about having many solutions with the form: as simple as possible for the gliders with a well-known diehard placed far away. For the title, something like "gliders as emergent properties" or something could also be catchy. \$\endgroup\$ Mar 24, 2021 at 22:01
5
\$\begingroup\$

I'm Jelly of Python (Cops)

I'm Jelly of Python (Robbers)

\$\endgroup\$
5
\$\begingroup\$

Decode Polybus Square/Tap Code/Prison Code

\$\endgroup\$
4
  • \$\begingroup\$ Nice challenge :) You need to add a scoring criterion (code-golf most likely), and you should provide a few input->output examples to help checking answers \$\endgroup\$
    – Leo
    Mar 22, 2021 at 23:03
  • \$\begingroup\$ Suggested testcases: 23 15 31 31 34 => HELLO, 24 25 31 32 => IJLM, 11 22 33 44 55 => AGNTZ. Add tags code-golf, decode and string. \$\endgroup\$
    – emanresu A
    Mar 23, 2021 at 8:11
  • \$\begingroup\$ Thanks for the feedback :) \$\endgroup\$ Mar 23, 2021 at 12:51
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted \$\endgroup\$ Mar 30, 2021 at 15:15
5
\$\begingroup\$

Plz Halp I Need $$$ Again

Bob’s startup is running out of money and desperately needs investors to keep it afloat. Although you have helped Bob find the maximum number of investors, Bob has quickly realized that more investors does not lead to more funds because different investors give different amounts of money. Each investor interested in Bob’s company wishes to schedule a meeting with a certain start and end time, and promises to invest a certain amount of money. However, some of the meetings times may conflict. What is the maximum amount of money he can get from his investors?

Input Format

Input is given as an array of tuples of integers (or the equivalent in your chosen language). Each tuple p represents one investor, where p[0] is the start time of the investor’s meeting, p[1] is the end time, and p[2] is the amount of money promised.

For example, in the test case [(0, 10, 30), (10, 20, 50)], there are two investors: one who wants to meet from time 0 to time 10 and offers $30, and one who wants to meet from time 10 to time 20 and offers $50.

Meetings will always have a positive duration, meeting times are always non-negative, and a meeting that ends at time k does not conflict with a meeting that starts at time k. You may assume that the input is nonempty, and you may use any reasonable I/O method for input.

Within reason, you may also take input in different formats (for example, as three lists, one which contains the start times, one with the end times, and one with the money offered).

Output

Your program should output an integer, the maximum quantity of money that Bob can make.

Test Cases

[(1, 100, 10), (1, 5, 3), (5, 10, 3), (10, 15, 3)] => 10
[(0, 30, 40), (20, 45, 30)] => 40
[(10, 40, 40), (60, 85, 60)] => 100
[(65, 100, 70), (10, 45, 80)] => 150
[(10, 15, 50), (50, 85, 10), (95, 110, 60)] => 120
[(100, 135, 80), (50, 70, 80), (80, 110, 30), (95, 100, 40)] => 200
[(65, 95, 70), (50, 75, 30), (35, 60, 80), (85, 115, 100)] => 180
[(30, 35, 80), (35, 65, 10), (75, 110, 40), (40, 45, 20)] => 140
[(80, 110, 50), (0, 5, 30), (95, 125, 50), (80, 85, 70)] => 150
[(25, 40, 10), (100, 115, 60), (15, 50, 90), (60, 95, 50)] => 200
[(100, 125, 50), (75, 80, 100), (30, 60, 20), (50, 65, 90)] => 240
[(15, 35, 80), (55, 70, 40), (30, 65, 90), (30, 55, 60)] => 120
[(15, 40, 50), (60, 95, 30), (35, 40, 70), (55, 60, 90)] => 190
[(40, 65, 80), (40, 75, 10), (5, 15, 80), (100, 115, 80), (15, 35, 100), (60, 95, 40)] => 340
[(5, 30, 60), (85, 105, 90), (35, 65, 80), (90, 115, 40), (85, 90, 80), (30, 60, 90)] => 270
[(55, 65, 30), (5, 15, 90), (50, 85, 100), (0, 15, 90), (65, 70, 70), (60, 70, 80), (35, 55, 20), (80, 105, 80)] => 290
[(0, 10, 90), (70, 85, 80), (45, 55, 20), (90, 105, 90), (55, 90, 50), (0, 25, 20), (85, 105, 30), (85, 90, 100)] => 380
[(10, 45, 40), (85, 115, 80), (85, 105, 30), (30, 50, 50), (20, 40, 80), (100, 115, 60), (100, 135, 70), (30, 35, 70), (35, 50, 30)] => 180
[(80, 105, 70), (60, 65, 50), (95, 105, 80), (55, 65, 100), (40, 75, 80), (95, 110, 70), (60, 70, 90), (65, 70, 50), (55, 85, 100)] => 230
[(80, 85, 70), (35, 40, 60), (60, 80, 80), (5, 20, 100), (30, 60, 100), (45, 50, 60), (45, 80, 60), (10, 20, 50), (50, 65, 60), (60, 85, 70)] => 370
[(50, 75, 100), (90, 115, 20), (50, 65, 10), (35, 50, 30), (90, 120, 90), (65, 90, 30), (20, 55, 40), (50, 75, 50), (75, 105, 10), (15, 35, 70)] => 290

Rules

  • Standard loopholes are prohibited.
  • Though not required, polynomial-time solutions are encouraged so that Bob does not have to wait forever for the result.
  • This is , so the shortest solution in each language wins.

Meta

  • Are there any errors with the computer-generated test cases? I've manually verified some of them but I may have overlooked something.
  • Is there any ambiguity in the problem statement?
  • Are there any other issues?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Test cases seems be ordered by end times. I'd suggest mixing them up (so no answer accidentally uses the order) or specifying the order. Also, in the example in the input format, it's (10, 20, 50) but you say they want to meet 5 - 10. (And I prefer the Output section before the test cases, so people know what they need to do earlier.) \$\endgroup\$
    – xash
    Apr 28, 2021 at 12:51
  • \$\begingroup\$ Thanks, I have edited the challenge accordingly \$\endgroup\$
    – knosmos
    Apr 28, 2021 at 12:55
  • 1
    \$\begingroup\$ Is it possible to take input as three lists, for start times, end times, and prices? \$\endgroup\$
    – rak1507
    Apr 28, 2021 at 13:13
  • \$\begingroup\$ Sure - should I add test cases in that format? \$\endgroup\$
    – knosmos
    Apr 28, 2021 at 13:16
  • 2
    \$\begingroup\$ You don't need to add testcases in different formats, simply state in your post that different formats are acceptable (and perhaps mention some different formats like the \$3\$ lists @rak1507 mentions). \$\endgroup\$
    – Noodle9
    Apr 28, 2021 at 13:41
  • \$\begingroup\$ Link to the deleted main post, so that it's easy to find and edit when this challenge is good to go :) \$\endgroup\$ Apr 28, 2021 at 15:21
5
\$\begingroup\$

posted

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I think I saw l4m2's proposal which is essentially the same thing, but this one is arguably much better and clearly worded. Btw, the first example is just a special case of Chaitin's constant with power-of-0.5 weights. \$\endgroup\$
    – Bubbler
    May 12, 2021 at 14:16
  • \$\begingroup\$ I don't see how it's possible, if \$f(n)\$ is computable, isn't the limit of \$f(n)\$ computable by the definition of limit? \$\endgroup\$ May 12, 2021 at 17:31
  • \$\begingroup\$ @CommandMaster Actually no! This is just one of a million ways in which limits can be counter intuitive. For an example, imagine an \$f\$ where \$f(n)\$ just takes the first \$n\$ Turing machines and runs them for \$n\$ steps, if machine \$m\$ halts in the test run then you add \$2^{-m}\$ to a total (think about what this means in binary). This is obviously computable, we can simulate Turing machines for \$n\$ steps and add rational numbers. But the limit encodes the exact solution to the halting problem. This is actually the first example number there. \$\endgroup\$
    – Wheat Wizard Mod
    May 12, 2021 at 17:48
  • 1
    \$\begingroup\$ Does \$f(n)\$ have to be an exact rational (i.e. a pair (numerator, denominator)), or can it be represented as a floating point number? In other words, can we output \$f(n)\$ as a floating point number which will, necessarily, be inexact for large values of \$n\$, as long as the algorithm theoretically works if given arbitrary precision? \$\endgroup\$
    – Delfad0r
    May 12, 2021 at 20:30
  • \$\begingroup\$ @Delfad0r I'm not entitled to answer your question, but I don't think float or double are applicable here. Arbitrary-precision floating-point numbers are certainly applicable tho. \$\endgroup\$ May 12, 2021 at 20:44
  • \$\begingroup\$ @WheatWizard Thanks for the clarification! Does the first option include, say, a pair [numerator,denominator] (even though it's not a built-in rational type)? In this case, is the pair required to be reduced (i.e. gcd=1)? \$\endgroup\$
    – Delfad0r
    May 13, 2021 at 10:09
  • 1
    \$\begingroup\$ @Delfad0r I will add that as another form, and the second format shows a non-reduced fraction as an example so it would be all right for this format as well. \$\endgroup\$
    – Wheat Wizard Mod
    May 13, 2021 at 10:11
5
\$\begingroup\$

Drop some boxes

\$\endgroup\$
1
  • \$\begingroup\$ Assuming you live in a world with gravity \$\endgroup\$
    – mathcat
    Jun 20, 2021 at 10:07
5
\$\begingroup\$

Ouput Input... Forever

Problem

Given input chars, output them repeatedly forever.

Examples

abc       -> abcabcabcabcabcabcabcabcabc...
[1, 2, 3] -> [1, 2, 3][1, 2, 3][1, 2, 3]...
lo        -> lololololololololololololol...

Dedication: This is for all the tarpits out there!

Questions

  • Should a delimiter be allowed?
  • I was imagining that the input would be cycled through infinitely in order, like in the examples. Should we enforce that as a rule, though?
    • Or should the rules just be: Each char of input should eventually occur infinitely many times in output. (Informally stated, but can easily be made mathematically precise.)
  • Other thoughts!
\$\endgroup\$
4
  • \$\begingroup\$ If you go with "Each char of input should eventually occur infinitely many times in output", then you'd need to specify that no other characters should be outputted because otherwise you could just output all bytes in order, or output random bytes infinitely \$\endgroup\$
    – pxeger
    Aug 6, 2021 at 7:24
  • \$\begingroup\$ I think that vast majority of languages here will just use some version of x = input(); while(true) {print(x);}, so I doubt this will be especially interesting except for in a handful of languages \$\endgroup\$ Aug 6, 2021 at 13:49
  • \$\begingroup\$ Are you going to post this? :) \$\endgroup\$
    – emanresu A
    Aug 13, 2021 at 22:30
  • \$\begingroup\$ Are you going to post this? It's been a month.... \$\endgroup\$
    – emanresu A
    Sep 6, 2021 at 3:31
1
4 5
6
7 8
132

You must log in to answer this question.

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