568
\$\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".

\$\endgroup\$
0

4564 Answers 4564

1
17 18
19
20 21
153
3
\$\begingroup\$

Speeding up powers of 2

Create a function or program that indefinitely prints outs successive powers of 2 separated by newlines. However, the nth term of the sequence (2^n) must have a delay of 1/n seconds either before or after it is printed, but please specify this in your answer. If you choose to add the delay before the number is printed, the first number may optionally have a delay before it is printed.

Your program may begin with 1 or 2 as the first printed number, but if you include 1, it is considered the 0th term, and your delays must be before each print and skip any initial delay (1/0 as a delay would not work, hence this rule).

Your program should run properly until it either reaches the integer limit of your language, or until n = 1000 (a 1 ms delay)

Expected output if 1 is included:

1 # after, wait 1/1 seconds
2 # after, wait 1/2 seconds
4 # after, wait 1/3 seconds
8 # after, wait 1/4 seconds
16 # after, wait 1/5 seconds
# etc...

Expected output if 1 is not included:

2 # before/after, wait 1/1 seconds
4 # before/aftert, wait 1/2 seconds
8 # before/after, wait 1/3 seconds
16 # before/after, wait 1/4 seconds
# etc...

Sandbox

  • How should I improve the wording?
  • What potential ambiguities or language limits are there?
  • Is this too similar to a preexisting challenge?

EDITS: Clarified that n refers to the term number, not the power of 2

\$\endgroup\$
13
  • \$\begingroup\$ I like the idea, but any language with arbitrary precision integers is disqualified because it's not possible (and it's not a small set of languages, a lot of languages support).. \$\endgroup\$ Jan 10, 2019 at 2:12
  • \$\begingroup\$ @BMO How is this impossible with arbitrary precision integers? Does it make it difficult to calculate the delays or is there some way in which printing some larger numbers make this impossible? Also, should I require that programs theoretically work for integers beyond the limit of the language (with minor modifications to account for this)? \$\endgroup\$
    – Neil A.
    Jan 11, 2019 at 4:31
  • \$\begingroup\$ The delay needs to be \$\frac{1}{n}\$, any system imposes some \$t_{\min}\$ which is required to output anything at all, as \$n\$ gets larger there will be some \$n_0\$ where \$\frac{1}{n_0} < t_{\min}\$ which is not possible. In short: The delay gets arbitrarily small while the work gets arbitrarily large and at some point this becomes infeasible. \$\endgroup\$ Jan 11, 2019 at 10:02
  • \$\begingroup\$ Are we allowed to sleep 1/1 seconds before printing 2 in the first iteration? Or are we allowed to print 1 and sleep 1/2 seconds afterwards in the first iteration? \$\endgroup\$ Jan 11, 2019 at 12:18
  • \$\begingroup\$ @BMO is indeed right that fairly quickly 1/n will become 0 in loads of languages. Java for example has a maximum precision of 16 decimal digits after the comma for floats/doubles (it does have BigDecimals for higher precision, but let's ignore those for now). The 64th iteration (number 18446744073709551616) will have a delay of 5.421010862427522e-17 ms, which is basically 0 in programming languages with 16 decimal digit precision. \$\endgroup\$ Jan 11, 2019 at 12:37
  • 1
    \$\begingroup\$ I do like the challenge in general, though (and have prepared a solution if it goes live), so +1 from me. :) \$\endgroup\$ Jan 11, 2019 at 12:37
  • \$\begingroup\$ @KevinCruijssen: You would have to either sleep for 1/1 and then print 1 initially, or sleep 1/2 seconds then print 2 initially, i.e. you must include the term associated with the delay. As for the second point, I would consider that to be starting with 1 and having the delay imposed before printing the `nth term, so it is valid. \$\endgroup\$
    – Neil A.
    Jan 11, 2019 at 15:26
  • \$\begingroup\$ @BMO: Should I instead make the sleep duration something like n^2, (2^n)/n, or another function that could make this interesting? (I want to avoid using simply n to make it a bit more interesting). I would change the title of the challenge appropriately, of course. \$\endgroup\$
    – Neil A.
    Jan 11, 2019 at 15:29
  • \$\begingroup\$ Choosing \$n^2\$ or even \$\frac{2^n}{n}\$ changes things massively. I like the idea of having less time for more work, but: 1) You need to set a boundary, st. the mentioned problem will not occur, if a submission chooses the right approach. 2) To make it interesting, I would balance the boundary and function in a way that the last iteration isn't too easy. \$\endgroup\$ Jan 11, 2019 at 17:17
  • \$\begingroup\$ A starting point (using a Unix system): Investigate how many CPU cycles a write syscall takes (let's assume \$1000\$ - I haven't checked though and it will depend a lot on the environment), assume a standard CPU clocked at \$1.5\$GHz, this gives you \$\frac{1000}{10^{9}\text{Hz}}=1\mu\text{s}\$ for a single write. A delay of \$\frac{1}{2^{31}}\$ (maximum power of two for \$\texttt{uint32}\$) is already half of that. \$\endgroup\$ Jan 11, 2019 at 17:17
  • \$\begingroup\$ @BMO: I may have messed up on my specifics, but what I intended was something along the lines of: when printing 2^31, there should be a delay of 1/31 seconds, not 1/(2^31). (n=the term number, not the power of two). \$\endgroup\$
    – Neil A.
    Jan 11, 2019 at 17:46
  • \$\begingroup\$ Ah, I misunderstood the challenge (I screwed up, not you). Delaying for \$\frac{1}{31}\$ of a second should be easy. You will still need to add a bound though. \$\endgroup\$ Jan 11, 2019 at 17:52
  • \$\begingroup\$ @BMO: Edited for clarity, limit is n=1000 (1 ms delay, should be handled by most languages fine) \$\endgroup\$
    – Neil A.
    Jan 11, 2019 at 17:59
3
\$\begingroup\$

Static Code Analysis Battle!

Your programs will play a friendly game of rock, paper, scissors. There's a catch though; you can not use randomness and the combatants can see each other's source code.

That is, you will write a python program that, when imported, provides a function named rps. Given two combatants, say player1.py and player2.py, the controller will import them, and execute player1.rps(player2sourceCode) and player2.rps(player1sourceCode). These should output R, P, or S. The winner is then whoever would win in rock paper scissors with those moves. If one player makes a valid move, and the other does not, that player wins. If both players make an invalid move, it is considered tie. Additionally, taking more than 1 second to move is considered an invalid move.

Here are the rules:

  1. Both the action of importing your module and your rps function should be pure functions. This means for example that you can not do the following:
    1. Use randomness or other non-deterministic code.
    2. Interfere with or receive information from the file system, I/O, peripherals, etc...
    3. Use time.sleep.
    4. Alter or access the state of the controller.
    5. Use other functions to do impure actions. For example, you can not call eval on the source code of an impure function call. An exception to this is if the only impure thing it does is interact with your program's state (i.e. it is permitted to change variables in your program's namespace). You can, however, call it on pure function call source code.
    6. Anything else that a pure function could not do.
  2. Other functions in your source code, however, may be impure.
  3. You may assume that the source code passed as an argument to rps obeys rule 1. You may not, however, assume that the rps in the passed source code is a pure function when you pass it source code that does not obey rule 1. Additionally, other functions in the module may be impure.
  4. Additionally, going into an infinite loop is perfectly fine, although if it happens when the caller calls your program, your move will be considered invalid. If the opponent calls your program and it causes them to go into an infinite loop, however, their move will be considered invalid, and vice versa.

This is , so the program that defeats the other programs wins! In particular, I will run a match between each program and each other program. The winner will be the condorcet winner if one exists. Otherwise, the result will be a tie between the Schwartz set members.

\$\endgroup\$
3
\$\begingroup\$

Classic VCS ASCII Adventure

Moved to main. Thanks everyone for your input. Happy golfing!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ This seems like a nice challenge! I'm not as experienced as other people around here, but you should publish it to main. \$\endgroup\$
    – MilkyWay90
    Jan 26, 2019 at 16:28
  • \$\begingroup\$ These question are likely to be asked: Can input be in decimal (some languages don't have "hex"-numbers and in other languages it's most of the time just a different literal but represents the same)? Can input be binary (maybe even as string)? Does "any character" include spaces? Is it restricted to printables only? Is returning an array of strings allowed or does it need to be a single newline-separated string? \$\endgroup\$ Jan 28, 2019 at 13:27
  • \$\begingroup\$ Maybe you could add an example with both x- and y-stretch factors being negative? \$\endgroup\$ Jan 28, 2019 at 13:30
  • \$\begingroup\$ @BMO thank you for your suggestions! I've updated the description to address your points. \$\endgroup\$
    – 640KB
    Jan 28, 2019 at 14:41
  • \$\begingroup\$ I've clarified a few things and added some better test cases. I'll wait to get a few more up-votes before submitting it though. \$\endgroup\$
    – 640KB
    Jan 28, 2019 at 17:36
  • \$\begingroup\$ Nice challenge! I've already prepared a solution in case it goes to main. Only perhaps slightly confusing part is where you use the byte-format 018H/024H in the circle example at the top, but then the format 0x18/0x24 in your test cases. I would change the 018H/024H in that first example to 0x18/0x24 as well to remain consistent across the entire challenge description. Apart from that everything is clear to me. \$\endgroup\$ Jan 29, 2019 at 13:42
3
\$\begingroup\$

The Forest Game (KotH, WIP)

Summary

You have been given a space of land to plant trees in. Unfortunately, due to an administrative mix-up, so have 4 other people. You are in a competition with them to make the most money out of your trees within the next 100 years.

The map

A 10 by 10 grid, representing the area of land. Each square will be one of the following:

  • A number, 0 to 4, representing a player
  • ., representing a seed (more later)
  • i, representing a sapling
  • T, representing a tree
  • F, an ongoing fire
  • , an empty space

Actions

Actions, given by your program, are 1 or 2 characters long. The first is the type:

  • . - plant a seed, costs 1
  • i - plant a sapling, costs 10
  • F - start a fire, costs 5
  • m - move, costs 0
  • w - work, gains 1 (what you do for easy points/to do nothing)
  • - - harvest, variable gains (see below)

Anything else as the first character will result in ignored command. The second character is one of `^'<>,v., a direction, which refers to the relative location of the square on which to perform the command:

` ^ '     NW N NE
<   > --> W     E
, v .     SW S SE

For the work command, the second character need not be present, but must be one of the eight if it is. An invalid command is ignored.

Growing

Seeds become saplings, saplings trees. After 5 rounds (25 turns), a seed becomes a sapling with the probability \$\frac{8 - C}8\$ where \$C\$ is the number of nearby (diagonally or orthogonally adjacent) saplings or trees. Saplings become trees after 7 rounds, with the same probability (\$C\$ here is only trees). This is worked out from the top left, going across each row in turn, meaning that each seed/sapling growth may be affected by saplings/trees created that turn.

Value

When harvested, saplings/trees add to your score. Saplings are valued at 15, trees at 20. After every round, a tree gains 1 point of value, up to a maximum of 40 points. Seeds cannot be harvested, nor can other players' saplings/trees.

Fires

Fires spread from the point you set them to all nearby trees and saplings, unless there is a player other than you also nearby. Example:

  T          T          T          T        
  i5         i5         F5          5       
TTTTTT --> FFTTTT -->   FTTT -->    TTT
F1 ii       1 ii       1 ii       1 ii      
  i          i          i          i        

Where 1 is you and 5 is the other player. Each step represents one turn (not one round).

Tournament

Each game, you start with 15 points, and loose/gain them as described in the 'actions' and 'value' sections. The aim is to be the player with the most points at the end of 100 rounds (500 turns in total). Each game will be played 6 times, and then repeated until one player has won more than any of the others. This collection of 6+ games is a 'match'. Every two days, if there have been new players added, the players will be split up into groups of 5, padded out with simple bots of mine if necessary. The winners of each of these will be split into groups of five and the above process repeated until there is only one group of five, the winner of which is the victor!

I/O

Your submission should be a Python 3 program, with a method run defined in the global scope. This method will be called with the following parameters:

  • map_ - a list of ten lists of single character strings. This will be a deep copy of the map, each string is one of 01234.iTF, representing that square.
  • round_ - the round number
  • points - a list of integers, representing the number of points each player has, in order.
  • num - whereabouts on the points list you come, also the number representing you and where you come in the turn order.

It should output the two/one character string mentioned above.

Controller

WIP, extremely buggy

'''
Rules
---
map, 20 by 20 squares,
starts empty with randomly placed players
square can be:
' ' - empty
'1' - [0-4], player
'.' - seed
'i' - sapling
'T' - tree
'F' - flames

actions:
'm' - move
'i' - plant sapling
'.' - plant seed
'-' - harvest tree
'F' - start fire
'w' - work (dir optional and ignored)
'?' - other, nothing

each action other than move should be accompanied by
a direction, [<>^v`,'.O] = (W,E,N,S,NW,SW,NE,SE,O)

flames:
 - go out if person nearby other than starter
 - turn every nearby tree/sapling to flames, 33% each
 - go out, leave ' '

costs/bonuses:
'm' - none
'i' - -10
'.' - -1
'-' - +15 for sapling, +20 for tree + turns living max. +40
'F' - -1
'w' - +1
'?' - none

growing:
. > l - (8-nearby [lT])/8 chance, after 5 turns
l > T - (8-nearby [T])/8 chance, after 7 turns
   T+ - +1 value every turn, max. 40

every five turns, tree drops a seed in an empty nearby square
start at 10 points
game end after 100 rounds

I/O
---
'''

import random, os, time, sys


class Item(object):
    def __init__(self, x, y, game, creator=None):
        self.x = x
        self.y = y
        self.game = game
        self.creator = creator


class Flame(Item):
    def update(self, around):
        burn = []
        for i in around:
            if str(i) in map(str, range(6)):
                if str(i) != str(self.creator):
                    return
            elif str(i) in 'Ti':
                burn.append(i)
        for i in burn:
            self.game.place(Flame, i.x, i.y, self.creator)
        self.game.place(Empty, self.x, self.y)

    def __str__(self):
        return 'F'


class Seed(Item):
    def __init__(self, x, y, game, creator, count=25, _next=None):
        _next = _next or Sapling
        super(Seed, self).__init__(x, y, game, creator)
        self.counter = count
        self.creator = creator
        self.next = _next

    def update(self, around):
        self.counter -= 1
        if self.counter:
            return
        pos = sum(str(x) in 'Ti' for x in around)
        if random.randrange(8) in range(pos):
            self.game.place(Empty, self.x, self.y)
            return
        self.game.place(self.next, self.x, self.y, self.creator)

    def __str__(self):
        return '.'


class Sapling(Seed):
    def __init__(self, x, y, game, creator):
        super(Sapling, self).__init__(x, y, game, creator, 35, Tree)

    def __str__(self):
        return 'i'

    def __int__(self):
        return 15


class Tree(Item):
    def __init__(self, x, y, game, creator):
        super(Tree, self).__init__(x, y, game, creator)
        self.val = 20

    def update(self, around):
        self.val += 1
        if self.val > 40:
            self.val = 40

    def __str__(self):
        return 'T'

    def __int__(self):
        return self.val


class Empty(Item):
    def update(self, around): pass

    def __str__(self):
        return ' '


class Player(object):
    def __init__(self, x, y, name, game):
        self.game = game
        self.x = x
        self.y = y
        self.name = name
        self.around = (None,) * 8
        self.points = 15

    def update(self, around):
        self.around = around

    def command(self, text):
        text = "mv"
        if len(text) != 2:
            if len(text) != 1:
                return
            else:
                self.points += text[0] == 'w'
                return
        dirs = "`^'<p>,v." #p = placeholder
        if text[1] not in dirs:
            return
        ny = self.y + (dirs.index(text[1]) % 3) - 1
        nx = self.x + int(dirs.index(text[1]) / 3) - 1
        if (nx, ny) == (self.x, self.y):
            return
        itm = self.around["`<,^v'>.".index(text[1])]
        if text[0] == 'w':
            self.points += 1
        elif ny < 0 or nx < 0 or not itm:    #remove for wrapping
            return
        if text[0] == 'm':
            if str(itm) == ' ':
                self.game.move(self.x, self.y, nx, ny)
        elif text[0] == 'F' and self.points > 0:
            if str(itm) in 'Ti':  #never!!!
                self.game.place(Flame, nx, ny, self)
                self.points -= 1
        elif text[0] == '.' and self.points > 0:
            if str(itm) == ' ':
                print('.')
                self.game.place(Seed, nx, ny, self)
                self.points -= 1
        elif text[0] == 'l' and self.points > 9:
            if str(itm) == ' ':
                print('l')
                self.game.place(Sapling, nx, ny, self)
                self.points -= 1
        elif text[0] == '-':
            if str(itm) in 'Ti':
                if itm.creator == str(self):  #never!!
                    self.game.place(Empty, nx, ny)
                    self.points += int(itm)

    def __str__(self):
        return str(self.name)


class Game(object):
    def __init__(self, players, names, size=20):
        self.map = []
        choose = []
        self.names = names
        for x in range(size):
            self.map.append([])
            for y in range(size):
                self.map[-1].append(Empty(x, y, self))
                choose.append((x, y))
        self.players = {}
        random.shuffle(choose)
        for i in range(len(players)):
            pos = choose.pop()
            p = Player(*pos, str(i), self)
            self.players[players[i]] = p
            self.map[pos[0]][pos[1]] = p
        self.round(1)

    def round(self, number):
        for i in self.players:
            self.updatemap()
            self.turn(i, number)
            if not 'idlelib.run' in sys.modules:
                time.sleep(0.04)
                os.system('cls')
                print(' |0 1 2 3 4 5 6 7 8 9')
                print('---------------------')
                [print(str(self.map.index(i)) + '|' + ' '.join(str(j) for j in i)) for i in self.map]
        if number != 100:
            self.round(number+1)
        else:
            [print(' '.join(str(j) for j in i)) for i in self.map]
            for i in self.players:
                print(names[i], self.players[i].points, sep=': ')

    def turn(self, player, rn):
        points = []
        n = 0
        for i in self.players:
            if i == player:
                num = n
            points.append(self.players[i].points)
        text = player(map_=[x[:] for x in self.map], num=num, points=points, round_=rn)
        self.players[player].command(text)

    def place(self, item_t, x, y, creator=None):
        try:
            itm = item_t(x, y, self, creator)
            self.map[x][y] = itm
            return itm
        except IndexError:
            pass

    def move(self, ox, oy, x, y):
        try:
            self.map[x][y]
            itm = self.map[ox][oy]
            self.place(Empty, ox, oy)
            self.map[x][y] = itm
            itm.x = x
            itm.y = y
        except IndexError:
            pass

    def updatemap(self):
        for x in range(len(self.map)):
            for y in range(len(self.map[x])):
                around = []
                for rx in (-1, 0, 1):
                    for ry in (-1, 0, 1):
                        if rx or ry:
                            try:
                                around.append(self.map[x+rx][y+ry])
                            except IndexError:
                                around.append('')
                if str(self.map[x][y]).strip():
                    print(' '.join(str(i) for i in around[:3]),
                          ' '.join(str(i) for i in around[3:6]),
                          ' '.join(str(i) for i in around[6:]),
                          str(self.map[x][y]), sep='\n', end='-----')
                self.map[x][y].update(around)


import burnitall, flamingworker, hardworker, plantandwait, seedandreap
allnames = ('Burn It All', 'Flaming Worker',
            'Hard-worker', 'Plant And Wait',
            'Seed And Reap')
allplayers = (burnitall, flamingworker, hardworker, plantandwait, seedandreap)

players = []
names = {}
for i in allplayers:
    players.append(i.run)
    names[i.run] = allnames[allplayers.index(i)]
Game(players, names, 10)
input()

Game results

Nothing yet!

Sandbox

  • Any thoughts? Do you like it?
  • All numbers, rules are undecided, tell me what you think I should change.
  • I know the controller has many bugs, I posted it here to show that one is being made but it's very much not ready to use.
  • That doesn't mean I don't want bug reports, if you use it and spot one, please tell me.
  • If you don't like Python - tough. It's all I've got on my computer*1, and I don't have space for much else.

*1 I tell a lie, I have got Java, but so much fuss in implementing it for one more language? I'll think about it...

\$\endgroup\$
2
  • \$\begingroup\$ I'd recommend cutting the probability aspect of saplings growing into trees and make it a variable growth rate based on neighbors. \$\endgroup\$
    – Beefster
    Apr 12, 2019 at 18:30
  • \$\begingroup\$ @Beefster Interesting. I'll think about that. \$\endgroup\$
    – Miriam
    Apr 12, 2019 at 19:51
3
\$\begingroup\$

Ragtag Band of Misfits

(Guaging interest)

This is a sort of sequel to Adventurers in the Ruins, taking place in a 2D dungeon, using a multi-agent team


A group of five adventurers enters a dungeon and wants to get the best loot. There are other parties competing for loot. Each party member has different abilities, health, stamina amounts, and carry capacity. Each has independent knowledge and must exchange information via a speak action.

The dungeon is made of rooms connected on a 2D grid. A room may have 1-4 doors. Some doors may be one-way. Rooms may have treasures, monsters, and traps.

As in the prequel challenge, treasure requires bidding and all actions resolve simultaneously with a specific priority on action types.

Party members

There are five classes of characters comprising each party

  1. Quartermaster
    • 100kg carry capacity, 10 HP, 1000 stamina, 5 power
    • Can heal party members in the same room
  2. Ranger
    • 50kg carry capacity, 10 HP, 1000 stamina, 8 power
    • Can see and attack monsters in adjacent rooms that are connected by a door
  3. Fighter
    • 50kg carry capacity, 25 HP, 1000 stamina, 8 power
    • Double damage to monsters
  4. Thief
    • 30kg carry capacity, 10 HP, 1500 stamina, 5 power
    • Automatically detects booby trapped treasures and can take them without triggering the trap
    • Can steal treasure from enemy adventurers in the same room
    • Can booby trap a treasure, making it appear twice as valuable, but dealing damage to whoever picks it up.
    • Effective bid on treasures is doubled. Wins ties on treasure bids except against other thieves.
  5. Wizard
    • 20kg carry capacity, 8 HP, 1500 stamina, 4 power
    • Can communicate telepathically with any single teammate without needing to be in the same room. This is a two-way channel of communication.
    • Can telepathically visit the room a teammate is currently in, seeing its contents and doors and enabling teleportation to that room
    • Can teleport self or ally in same room to any previously visited room or the same room as any ally.
    • Can teleport any ally to the current room
    • Carried treasure does not increase cost for moving between rooms or teleporting
    • Deals half damage to monsters

Actions available to adventurers of all classes

  • Move between rooms
  • Exit the dungeon (if in the starting room)
  • Speak (can be combined with certain actions)
  • Send a message to the wizard
  • Pick up a treasure (bidding rules work the same as the first challenge)
  • Gift a treasure to another party member in the same room
  • Drop a treasure
  • Attack a monster
  • Attack a rival adventurer in the same room
  • Guard (prevent oncoming attacks and theft attempts)
  • Wait

Communication

Adventurers can communicate by speaking, which will be heard by all teammates in the same room. Speaking requires no stamina and can be combined with movement or gifting, but is limited to be a 20-character string. (Use of emojis for increased message density is fair game)

Combat

A power must be specified when attacking a monster. This cannot be higher than the adventurer's power rating. That amount of stamina will be expended and the monster will be damaged by that amount. If the monster is still alive after all attacks have resolved, the monster will then deal its damage split among all combatants that attacked that turn, minimum of 1 damage.

If adventurers are outnumbered by monsters in any room, the monsters will attack anyone attempting to pick up treasure for 1 damage each.

Defeating a monster will cause the monster to drop up to 3 treasures (typically more valuable than the others in the room) and the characters who attacked the monster that turn will level up, gaining 1 power.

Attacking a rival adventurer will deal one fifth of the damage normally dealt to monsters, but will not result in a counterattack. Attacking an adventurer who either guards or moves into another room will result in a miss. It is possible for adventurers to kill each other on the same turn since attacks resolve simultaneously.

Coding

You will write a bot for each party member. They may not share data (other than constants and libraries).

\$\endgroup\$
3
\$\begingroup\$

Battle of Wits (Where is the Poison?)


The battle of wits is a well-known scene from the Princess Bride.

Two bots will face off in a battle of wits: one poisons a wine goblet and the other chooses which to drink from (the other player drinks from the other goblet). Whoever drinks the poison loses. This will be repeated until one bot wins 20 rounds, with who poisons the goblet being randomized each time. Each match, you will be able to see the entire history of which goblet was chosen and you will also have access to the other player's decision function (Related). All submissions will be evaluated in a round-robin tournament, with ties being broken by who has the fewest losses across all games. Further ties will be resolved by who has the fewest losses to the contesting opponents. If there is a perfect intransitive relationship among three or more bots, all of them will be considered tied for first place.


This is equivalent to the matching pennies game in terms of who wins a round. The poisoner is equivalent to the penny matcher and the chooser is equivalent to the non-matcher.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ How about, to make it more interesting, let the bots read each other's source code? \$\endgroup\$
    – Jo King Mod
    Apr 19, 2019 at 4:51
  • 1
    \$\begingroup\$ @JoKing ooh. That's genius! Similar to this? \$\endgroup\$
    – Beefster
    Apr 19, 2019 at 6:00
3
\$\begingroup\$

Output the Visible Spectrum in RGB

Inspired by http://www.physics.sfasu.edu/astro/color/spectra.html

Light with wavelength between ~380 and 780 nanometers is considered to be within the visible spectrum. One can approximate the colors of the visible spectrum in RGB space by linearly interpolating the wavelength at specific ranges. The ranges and corresponding formulae for a wavelength wl are given below, assuming each color value is a real between 0 and 1:

  • [380-440): r = (440 - wl) / (440 - 380), g = 0, b = 1
  • [440-490): r = 0, g = (wl - 440) / (490 - 440), b = 1
  • [490-510): r = 0, g = 1, b = (510 - wl) / (510 - 490)
  • [510-580): r = (wl - 510) / (580 - 510), g = 1, b = 0
  • [580-645): r = 1, g = (645 - wl) / (645 - 580), b = 0
  • [645-780): r = 1, g = 0, b = 0

Note that in this system, the interpolation formula is cyclic with the color components, and changes sign with respect to the range maximum or minimum.

The challenge

Given an integer wavelength between 380 and 780, output the RGB value using the above interpolations.

Output may be a list of floats in [0,1] or integers between [0,255] in the format (r,g,b), or a valid RGB hex code.

This is code golf, so the shortest code in bytes wins!

Test cases

Rounding errors to within 0.01 in float format or to within 1 in integer format are acceptable.

wl=400 --> (0.29, 0.0, 0.65) or (73,0,165) or #4900A5
wl=530 --> (0.28, 1.0, 0.0)  or (72,255,0) or #48FF00
wl=640 --> (1.0, 0.07, 0.0)  or (255,19,0) or #FF1300
wl=750 --> (1.0, 0.0, 0.0)   or (255,0,0)  or #FF0000

Bonus

At extreme ranges of the visible spectrum, human perception is not as good. This can be modeled as a loss of intensity by multiplying the RGB values computed above by a factor f for specific cutoff points:

  • wl < 420: f=0.3+0.7*(wl-380)/(420-380)
  • wl > 700: f=0.3+0.7*(780-wl)/(780-700)

The total (r,g,b) including the perception factor is therefore (f*r, f*g, f*b)

\$\endgroup\$
2
  • \$\begingroup\$ I changed your post slightly; feel free to revert if you dislike my changes. \$\endgroup\$ May 3, 2019 at 20:19
  • \$\begingroup\$ I also want to notify you of the fact that we have MathJax enabled, so you could TeX your equations. \$\endgroup\$ May 3, 2019 at 20:22
3
\$\begingroup\$

Approximating Roots

(If you can think of a better title, then please suggest it!)

One day, when I was bored in maths class, I learned of a neat trick for solving the real cube root of a number!

Let's use the number \$79,507\$ as an example.

First, take digit in the one's place and compare it to this table:

\begin{array} {|r|r|} \hline \text{Extracted Digit} &\text{Resulting Digit} \\ \hline \text{1} &\text{1} \\ \text{2} &\text{8} \\ \text{3} &\text{7} \\ \text{4} &\text{4} \\ \text{5} &\text{5} \\ \text{6} &\text{6} \\ \text{7} &\text{3} \\ \text{8} &\text{2} \\ \text{9} &\text{9} \\ \text{0} &\text{0} \\ \hline \end{array}

In this example, the Resulting Digit will be \$3\$ since the digit in the one's place is \$7\$.

Next, remove all digits that are less than \$10^3\$:

$$ 79507 → 79 $$

Then, find the largest perfect cube that does not exceed the input:

$$ 64 < 79 $$

\$64=4^3\$, thus the next digit needed is \$4\$.

Finally, multiply the digit found in the previous step by \$10\$ and add the Resulting Digit found in the first step:

$$ 10*4+3=43 $$

Thus, the cube root of \$79,507\$ equals \$43\$.

However, there a neat quirk about this trick: it doesn't apply to only cubed numbers. In fact, it works with all \$n>1\$ where \$n\bmod2\ne0\$.

The steps mentioned above can be summed up in this generalization for an \$n\$ power:

  • Step 1) Take the digit in the one's place in the input. Compare it to the one's place digit of the \$n\$th powers of \$1\$ to \$10\$, then use the corresponding digit.

  • Step 2) Remove all digits of the input less than \$10^n\$. Compare the resulting number to the perfect powers definied in Step 1. Use the \$n\$th root of the largest perfect power less than said number.

  • Step 3) Multiply the number from Step 2 by 10 then add the number from Step 1. This will be the final result.

Task

Given two positive integers \$n\$ and \$m\$, return the \$n\$th root of \$m\$.

Input:

  • Two positive integers \$n\$ and \$m\$.

  • \$m\$ is guaranteed to be a perfect \$n\$th power of an integer.

  • \$n\$ is guaranteed to be odd and greater than \$2\$. (This method doesn't work if \$n\$ is even.)

Output:

  • The \$n\$th root of \$m\$.

Rules:

  • This is , so the fewer bytes, the better!

  • Standard I/O rules apply.

  • The output must be calculated using the aforementioned method.

  • No builtins allowed that already calculate this. A prime example being TI-BASIC's x√ command.

\$\endgroup\$
9
  • \$\begingroup\$ That's a pretty neat trick! I guess I'm not the only one who gets bored in math class. Also, I think you made an error on your test case, it says 10 x 4 + 4 rather than + 3 \$\endgroup\$ May 5, 2019 at 14:03
  • \$\begingroup\$ @RedwolfPrograms yes, I believe so! Guess my finger slipped on the keyboard \$\endgroup\$ May 5, 2019 at 16:31
  • \$\begingroup\$ Is there anything else I should change about this post before I post it on main? Not sure what to call this challenge tbh \$\endgroup\$ May 5, 2019 at 20:05
  • \$\begingroup\$ At the beginning of the question, it states that the method only works on perfect cubes, but it later says that it works on all odd numbers > 2. Other than that I don't see many issues, but I'd leave it here for a day or so just in case. \$\endgroup\$ May 5, 2019 at 20:09
  • \$\begingroup\$ Good point! I think that I should remove that line, as it is invalidated later on, as you said. \$\endgroup\$ May 5, 2019 at 20:18
  • \$\begingroup\$ Posting to main! Let's hope that this challenge fares well. \$\endgroup\$ May 7, 2019 at 13:25
  • \$\begingroup\$ "The output must be calculated using the aforementioned method" falls foul of Things to avoid: Non-observable program requirements. \$\endgroup\$ May 7, 2019 at 14:18
  • \$\begingroup\$ @PeterTaylor it may not be observable directly, but the source code will be able to indicate whether the method was used or not. \$\endgroup\$ May 7, 2019 at 14:25
  • \$\begingroup\$ @Tau, read the answer I linked. It explicitly addresses that point. \$\endgroup\$ May 7, 2019 at 14:51
3
\$\begingroup\$

Golf my Ada arrays

Background

Ada is a programming language that is not exactly known for its terseness.

However, its array literal syntax can in theory allow for fairly terse array specifications. Here is a simple EBNF description of the array literal syntax (passable to bottlecaps.de:

array ::= positional_array | named_array
positional_array ::= expression ',' expression (',' expression)*
named_array ::= component_association (',' component_association)*
              | expression (',' expression)* ',' 'others' '=>' expression
component_association ::= discrete_choice_list '=>' expression
discrete_choice_list ::= discrete_choice ('|' discrete_choice)*
discrete_choice ::= expression ('..' expression)?

We will limit ourselves to 1-dimensional arrays of integers for simplicity. This means that we will use only integers for the expression values. Perhaps in a future challenge we could try something more advanced (like declaring variables and multidimensional arrays). You do not have to golf the integer literals.

Challenge

The goal of this challenge is to output the shortest byte-count Ada array literal for a given input array. Note that Ada arrays can start from whatever index is desired, so you can pick what you wish the starting index to be as long as each value is sequential. In this example I choose to start at 1, which is idiomatic for Ada, however you can choose to start at any other integer.

Input

Your input will consist of a list of integers, in whatever form is convenient.

Output

Your output will be a string of text representing the shortest valid Ada array literal that represents the list of input integers. You may use any starting index you wish on this array, but your choice (whatever it is) must be specified in your answer (the starting index may also be dynamic).

Do not modify the representation of the input integers, keep them in decimal format. This challenge does not cover golfing of integer values.

Examples

Here are some examples:

Simple: [1, 2, 3] -> (1,2,3)
Range: [1, 1, 1, 1, 1, 1, 1,] -> (1..7=>1)
Others: [1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1] -> (6=>2,others=>1)
Multiple Ranges: [1,1,1,1,1,2,2,2,2,2,1,1,1,1,1,2,2,2,2,2,1,1,1,1,1] -> (6..10|16..20=>2,others=>1)
Tiny Ranges: [1,1,2,2,1,1,1,1,1] -> (3|4=>2,others=>1)
Far Range: [[1]*5, [2]*100, [3]*5] -> (1..5=>1,6..105=>2,others=>3)
Alternation: [1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2] -> (1|3|5|7|9|11|13|15|17=>1,others=>2)
Big Number: [1234567890,1,1234567890] -> (2=>1,1|3=>1234567890)
Big-ish Number: [1234567,1,1234567] -> (1234567,1,1234567)

Minimum Requirements

  • Support at least 100 numbers and inputs of at least 256 numbers in length.

  • Produce the correct result for all such inputs (including putting 'others' at the end)

  • Terminate (preferably on TIO) for each of the above inputs in under a minute.

Reference Implementation

Try it online!

This implementation uses the input as its array, with each character being a number. Capital letters are special constants for large values. The program argument is the 'start index' to use.

The "code" section in the TIO link is a correct solution to the problem, while the "header" and "footer" implement the test structure.

\$\endgroup\$
6
  • \$\begingroup\$ Your syntax doesn't match the examples; although I don't know Ada, I do know VHDL (which uses the same array syntax), and I think allowing others => in a named array (like the examples do, and the syntax doesn't) is correct. As for the challenge more generally, the specification is clear but you're missing a victory condition. code-golf is our most common victory condition here because it works well for a wide range of problems; I don't see any reason why it would work badly for this one, and don't think any of the usual alternatives are better. \$\endgroup\$ May 7, 2019 at 22:43
  • \$\begingroup\$ Oh, one other suggestion is that having more functionality in the reference implementation than is required in users' answers is confusing. You might want to try explaining more clearly what the linked TIO program does, and explaining it as something like "a tool to try out various inputs, supporting abbreviations for some larger inputs, and seeing what the intended output is". \$\endgroup\$ May 7, 2019 at 22:50
  • \$\begingroup\$ One other thing that could improve the question: specify what sort of input the program should take (presumably a list of integers), and what sort of output the program should produce (presumably a string). You don't need to define terms like "list" and "string" precisely; people will use whatever definitions make sense for their language. You should probably say something like "for the purposes of this challenge, numbers in the output should be in decimal; you do not have to golf them", because golfing of the output integers could change their length and thus which array syntax is optimal. \$\endgroup\$ May 7, 2019 at 22:53
  • \$\begingroup\$ I've added some clarifications. \$\endgroup\$
    – LambdaBeta
    May 9, 2019 at 14:51
  • \$\begingroup\$ "Do not modify the representation" is a bit unclear: the language that people use might be taking input in a format other than decimal, but in that case we still want decimal in the output. Apart from that, I think everything is fine now (and that particular issue isn't unclear enough to make the question closeable, IMO, although close votes are often hard to predict). \$\endgroup\$ May 13, 2019 at 16:22
  • \$\begingroup\$ I see what you mean, I'll adjust that and post it. Thanks for the help! \$\endgroup\$
    – LambdaBeta
    May 13, 2019 at 16:35
3
\$\begingroup\$

Arithmetic quine

Write a quine.
Well that's not very original challenge so let's spice things up.

Challenge

Write a quine which when once or multiple times appended to itself (see Appending) then performs an arithmetic operation of your choice.
You can implement as many operations from the as you want (see Scoring, Operations)

Example:
Let's say my code were foobar. This would return foobar because it's a quine.
Now foobarfoobar would preform + operation on two input numbers.
foobarfoobarfoobar could preform a * operation.

Note: which operation you choose for whatever number of appended copies doesn't matter but you have to write it down in your answer.

Example: Your code might be 4 times appended to preform addition, or it might need to be appended 5 times. It doesn't matter as long as you write the full list of the operations you implemented and the number of concatenations needed.

Operations

The list of operations you are allowed to implement is:

Addition
Subtraction
Multiplication
Integer Division
Integer exponentiation
Integer Factorial

Scoring

score = bytes/(n_operations + 1)

Bytes mean the bytes of the initial un-appended program.

Appending

All languages (even if 2D) must be appended by simply concatenating the program two or more times.

\$\endgroup\$
15
  • \$\begingroup\$ What operations should I add or how should I make this more clear? \$\endgroup\$
    – IQuick 143
    Apr 29, 2018 at 7:37
  • 2
    \$\begingroup\$ If not duplicate it be good \$\endgroup\$
    – l4m2
    Apr 29, 2018 at 11:14
  • \$\begingroup\$ I expect that this would be extremely difficult. Hyperprogramming is a similar challenge with only addition, multiplication, and exponentiation where its achievability was called into question. \$\endgroup\$ Apr 30, 2018 at 6:19
  • 3
    \$\begingroup\$ In my opinion, all languages should be treated equally. Otherwise there would be a lot of disputes (for example: (1) what about Cubix or Hexagony or Wumpus or Quadrefunge, where the layout is not directly rectangular but still >1D? (2) if my language is not 2D can I append horizontally? (3) Can I use a codepage where newline is a different character from \x10? ) \$\endgroup\$
    – DELETE_ME
    May 2, 2018 at 12:22
  • \$\begingroup\$ Can we read our own source code, or do default loopholes and quine rules apply? \$\endgroup\$ May 8, 2019 at 13:30
  • 1
    \$\begingroup\$ @EsolangingFruit I have the feeling this challenge is easier than that one though. Appending the entire source code allows you to utilize the length, whereas duplicating every character gives all kind of trouble which is harder to overcome/ignore. PS: I've prepared a solution which works with all six operations. Those operations are just examples, right? I could add more if I want to? \$\endgroup\$ May 8, 2019 at 13:49
  • \$\begingroup\$ Prepared a solution with nine operations, and will add more later on. :) Looking forward seeing this go live. \$\endgroup\$ May 8, 2019 at 13:57
  • \$\begingroup\$ @KevinCruijssen May I know which operations, I'll probably add them to the list \$\endgroup\$
    – IQuick 143
    May 8, 2019 at 14:05
  • \$\begingroup\$ @KevinCruijssen The list was supposed to be a full list but I don't see why we couldn't expand it, also I'm considering adding a score to each operation, since some are harder to accomplish than others. \$\endgroup\$
    – IQuick 143
    May 8, 2019 at 14:09
  • 1
    \$\begingroup\$ @IQuick143 Well, the ones I have right now are: addition; subtraction; multiplication; integer division; exponentiation; factorial; square; square-root; 1/n. But I could easily add more like regular division; modulo; +1; +2; -1; -2; signum; absolute difference; base-conversion to; base-conversion from; xor; bitwise-and; bitwise-or; negate; halve; double; length; etc. etc. haha ;p So maybe it's good to have a list instead of leaving the choice to everyone. ;) I would personally use add; subtract; divide; int-divide; multiply; exponent; modulo (all requiring two inputs) \$\endgroup\$ May 8, 2019 at 16:48
  • 1
    \$\begingroup\$ But I'll leave the choice to you. If you want to keep the original six operators that's fine as well. (In which case I would change the sentence to "The list of operations you are allowed to implement:") \$\endgroup\$ May 8, 2019 at 16:50
  • \$\begingroup\$ @KevinCruijssen I was thinking of changing the metric to score = bytes * (operations_language_can_implement - implemented_operations + 1), because some languages might not be able to handle floats for instance, what do you think? \$\endgroup\$
    – IQuick 143
    May 11, 2019 at 13:46
  • \$\begingroup\$ @JoKing Thanks for the grammar help. \$\endgroup\$
    – IQuick 143
    May 11, 2019 at 13:47
  • \$\begingroup\$ @IQuick143 Doesn't that give an unfair advantage to those languages? Let's say language A can and has implemented 5 operations in X+5 bytes. And language B can and has implemented 10 operations in X+10 bytes. Although both will get get 1 in the (operations_language_can_implement - implemented_operations + 1) part of your scoring, the byte-count of B is X+10, so 5 bytes higher than A's X+5, even though it implemented more operations.. I would keep the scoring as is, and have a select list of operations to implement. If a language can't handle it, it's score would be higher to reflect that. \$\endgroup\$ May 13, 2019 at 9:06
  • \$\begingroup\$ And if you want to keep it with integers only, you could perhaps use the following six operation all requiring two inputs: add; subtract; int-divide; multiply; exponent; modulo? \$\endgroup\$ May 13, 2019 at 9:07
3
\$\begingroup\$

Print some very large numbers

Not sure if this has been done before. Write a program that takes in a scientific format number (as two inputs, a mantissa and an exponent), and outputs a decimal representation of that number (as a string). The trick is that this must go far beyond most languages number limits.

The mantissa will always be within 1 ≤ mantissa ≤ 10 or mantissa = 0.

The exponent will always be a 32-bit signed integer.

Example:

1, 100 -> 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

3.543235, 200 -> 354323500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

3.3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333, 10 -> 33333333333.333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

5.3282, -71 -> 0.000000000000000000000000000000000000000000000000000000000000000000000053282

0, 999999 -> 0
\$\endgroup\$
5
  • 3
    \$\begingroup\$ Nice challenge, but can we use our language's scientific notation, E.g. some languages don't use the +, or use a different minus? \$\endgroup\$
    – Adám
    May 20, 2019 at 11:09
  • 2
    \$\begingroup\$ Maybe even allow taking mantissa and exponent as separate inputs? \$\endgroup\$
    – Adám
    May 20, 2019 at 11:12
  • 1
    \$\begingroup\$ Don't forget to add some example cases with negative exponent and one with an integer mantissa. Oh, and also a 0 case. \$\endgroup\$
    – Adám
    May 20, 2019 at 11:13
  • 1
    \$\begingroup\$ Will input always be in canonical format; 1≤|mantissa|<2 or mantissa=0. Can there be leading and trailing 0s in input? How about in output? \$\endgroup\$
    – Adám
    May 20, 2019 at 11:15
  • 2
    \$\begingroup\$ I like the idea of taking the mantissa and exponent as seperate inputs. Then we can do away with the string parsing part of the challenge and just focus on handling big numbers (by giving the inputs as floating point numbers). \$\endgroup\$
    – Omegastick
    May 21, 2019 at 1:15
3
\$\begingroup\$

Do X with Y

Your task is to create a X made of nested 3x3 lowercase Ys, with n levels of nesting. Here is how a X looks like (this is also the output for n = 0):

y y
 y
y y

A 0-level nested lowercase Y is just y. To nest a lowercase Y a level further, you arrange 4 copies of it like this:

y y
 y
y

Here is the output for n = 1:

y y   y y
 y     y 
y     y  
   y y
    y
   y
y y   y y
 y     y 
y     y  

Here is the output for n = 2 (I typed all of this by hand; excuse any mistakes):

y y   y y         y y   y y
 y     y           y     y 
y     y           y     y
   y y               y y
    y                 y
   y                 y
y y               y y
 y                 y
y                 y
         y y   y y
          y     y
         y     y
            y y
             y
            y
         y y
          y
         y
y y   y y         y y   y y
 y     y           y     y
y     y           y     y
   y y               y y
    y                 y
   y                 y
y y               y y
 y                 y
y                 y

Input

A non-negative integer n. You may choose the levels of nesting to be either 0- or 1- indexed.

Output

A X made of nested 3x3 lowercase Ys, with n levels of nesting, as a string, list of lines as strings, or outputted directly.

Sandbox stuff

  • Is anything missing?
  • Is the specification of the X clear enough?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ heavily related question. I'm not 100% convinced this is different enough to not be a dupe, but I'd try to get some more feedback before posting/abandoning this. \$\endgroup\$
    – Giuseppe
    Jun 3, 2019 at 21:37
  • 2
    \$\begingroup\$ I think this would be a duplicate. My experience with porting an answer from yet another 3*3 fractal challenge was that I only needed to make a small change in the code. \$\endgroup\$
    – xnor
    Jun 4, 2019 at 4:49
  • \$\begingroup\$ I have no idea if should I post this or not, as this both is +3 and seems to receive feedback as a possible duplicate. \$\endgroup\$ Jun 13, 2019 at 14:53
3
\$\begingroup\$

Atomic Handshakes

Introduction

Here you are. At a party, with two drinks in your hands. Your friend just went to the bathroom and you don't really know anyone else here. And so you wait. Or do you?

There is a century old hypothesis known as Six Degrees of Separation. The hypothesis states, that any other person in the world is connected to you as a friend of a friend of a friend etc.. It would essentially only take you six handshakes to connect with any other person on this planet. But is there actually any truth in this hypothesis? That's what we're about to find out in this challenge!

A similar question also finds its way into my own field of expertise: chemistry. Hence the title. Chemistry is the study of molecules, and molecules get very complex very fast. All (for the sake of simplicity) atoms in a molecule are connected. For certain types of analysis, one may need to know how many connections (bonds) it takes to get from one atom to another.

The Challenge

In a set of N people, each person has a maximum of N-1 direct connections. Based on this information, it is your task to deduce for every person what the lowest number of connections is to get to every other person.

People (and atoms too) can have similar names. Therefore, instead of a name, every person will get a unique identifier. To make things easy, the identifier will be a non-negative integer and the integers are all consecutive. How convenient!

Input

An array-like object of size N which lists the first-degree connections for each person.

Output

A two-dimensional, symmetrical array of size NxN which shows for each person the shortest distance to every other person.

Challenge rules

  • All people are connected: there are no loners or isolated groups in the input
  • Circular connections are allowed, but
  • Only the shortest connection must be output as more ways lead to Rome

General rules

Examples

As the theory may still be somewhat confusing, I will include a network graph for each example. This should make it a lot easier to understand what we're talking about. Here goes!

Example 1

Consider the connected set

0---1---2---3
        |   |
        4---5---6

For this network, our input array will be

[[1]          # Since 0 is connected only to 1
 [0 2]        # Since 1 is connected to 0 and 2
 [1 3 4]      # Since 2 is connected to 1, 3 and 4
 [2 5]        # Et cetera
 [2 5]
 [3 4 6]
 [5]]

Which should result in the following output (excluding comments):

# Distance from
# 0 1 2 3 4 5 6
                   # To
[[0 1 2 3 3 4 5]   # 0
 [1 0 1 2 2 3 4]   # 1
 [2 1 0 1 1 2 3]   # 2
 [3 2 1 0 2 1 2]   # 3
 [3 2 1 2 0 1 2]   # 4
 [4 3 2 1 1 0 1]   # 5
 [5 4 3 2 2 1 0]]  # 6

Example 2

Consider the connected set

.-------.
|       |
|   0   |
|   |   |
|   1---2---3---.
|   |   |   |   |
'---4---5---6   |
    |           |
    7---8---9---'

For this network, our input array will be

[[1]          # Since 0 is connected only to 1
 [0 2 4]      # Since 1 is connected to 0, 2 and 4
 [1 3 4 5]    # Since 2 is connected to 1, 3, 4 and 5
 [2 6 9]      # Et cetera
 [1 2 5 7]
 [2 4 6]
 [3 5]
 [4 8]
 [7 9]
 [3 8]]

Which should result in the following output (excluding comments):

# Distance from
# 0 1 2 3 4 5 6 7 8 9
                         # To
[[0 1 2 3 2 3 4 3 4 4]   # 0
 [1 0 1 2 1 2 3 2 3 3]   # 1
 [2 1 0 1 1 1 2 3 3 2]   # 2
 [3 2 1 0 2 2 1 3 2 1]   # 3
 [2 1 1 2 0 1 2 1 2 3]   # 4
 [3 2 1 2 1 0 1 2 3 3]   # 5
 [4 3 2 1 2 1 0 3 3 2]   # 6
 [3 2 3 3 1 2 3 0 1 2]   # 7
 [4 3 3 2 2 3 3 1 0 1]   # 8
 [4 3 2 1 3 3 2 2 1 0]]  # 9

Example 3

Consider the connected set

.---0---.
|   |   |
1---2---3
|   |   |
'---4---'

For this network, our input array will be

[[1 2 3]      # Since 0 is connected to 1, 2 and 3
 [0 2 4]      # Since 1 is connected to 0, 2 and 4
 [0 1 3 4]    # Et cetera
 [0 2 4]
 [1 2 3]]

Which should result in the following output (excluding comments):

# Distance from
# 0 1 2 3 4
               # To
[[0 1 1 1 2]   # 0
 [1 0 1 2 1]   # 1
 [1 1 0 1 1]   # 2
 [1 2 1 0 1]   # 3
 [2 1 1 1 0]]  # 4
\$\endgroup\$
1
  • 2
    \$\begingroup\$ In short, all pairs shortest path. Single-route shortest path would definitely be closed as a duplicate; I would say there's a significant chance that the consensus will be that this is also a duplicate of one of the questions in path-finding. \$\endgroup\$ Jul 5, 2019 at 10:59
3
\$\begingroup\$

Too many spies

You are fighting an extensive network of enemy spies. You know that each spy has at least one (sometimes multiple) fake identities they like to use. You'd really like to know how many spies you're actually dealing with.

Luckily, your counter-intelligence agents are doing their job and can sometimes figure out when two fake identities are actually controlled by the same enemy spy.

That is to say:

  • Your agents don't always know when two fake identies have the same spy behind them, however
  • If an agent tells you two fake identities are controlled by the same spy, you trust they are right.

Agent messages

Agents send you cryptic messages telling you which identities have the same spy behind them. An example:

You have 2 agents and 5 fake identities to deal with.

The first agent sends you a message:

Red Red Blue Orange Orange

This means they think there are 3 spies:

  • the first one (Red) controlls identities 1 and 2
  • the second one (Blue) controlls identity 3
  • the third one (Orange) controlls identities 4 and 5

The second agent sends you a message:

cat dog dog bird fly

This means they think there are 4 spies:

  • the first one (cat) controlls identitiy 1
  • the second one (dog) controlls identities 2 and 3
  • the third one (bird) controlls identity 4
  • the fourth one (fly) controlls identity 5

Compiling the intel we see:

Identities:   id1    id2    id3    id4    id5 
Agent 1:    |--same-spy--|       |--same-spy--|
Agent 2:           |--same-spy--|
Conclusion: |-----same-spy------||--same-spy--|

This means there are at most 2 spies.

Notes

Identities owned by the same spy do not have to be consecutive, i.e. a message like:

dog cat dog

is valid.

Also, the same word might be used by two different agents - that does not mean anything, it's just a coincidence, e.g.:

Agent 1: Steam Water Ice
Agent 2: Ice Ice Baby

Ice is used by both agents - the Ice used by the first agent is unrelated to the two occurences of Ice used by the second agent.

Challenge

Compile all your agents' intel and figure out how many enemy spies there really are. (To be more precise, get the lowest upper bound, given the limited information you have.)

The shortest code in bytes wins.

Input and Output spec

The input is a list of n lines, which represent n messages from agents. Each line consists of k space-separated tokens, same k for all lines. Tokens are alphanumeric, arbitrary length. Case matters.

The output should be a single number, representing the number of distinct spies, based on your agents' intel.

Examples

Example 1

Input:

Angel Devil Angel Joker Thief Thief
Ra Ra Ras Pu Ti N
say sea c c see cee

Output:

2

Example 2

Input:

Blossom Bubbles Buttercup
Ed Edd Eddy

Output:

3

Example 3

Input:

Botswana Botswana Botswana
Left Middle Right

Output:

1

Example 4

Input:

Black White
White Black

Output:

2
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The core problem of union set is nicely presented, but the input requirements are rather too restrictive. The question will be better received if the input is permitted to be received as an array of arrays or any other reasonable list format. See codegolf.meta.stackexchange.com/q/7853/194 \$\endgroup\$ Jul 16, 2019 at 8:22
3
\$\begingroup\$

Originally posted on main site, moved here for more suggestions. Better scoring mechanics required.

Introduction

I've been browsing all those challenges and was thinking "yeah, they're good, but what if we make GoL one?", so here it goes.

Challenge

Build starting setting for either Conway's Game of Life or other similar cellular automaton (restricted to ones with binary cell state) which after known amount of generation will include square area containing representation of QR code decodable to string "Hello, world!".

  • Cell (non-empty state) is interpreted as black pixel, no cell as white.
  • Your automation should take at least one generation until result (no hardcoded results allowed).
  • Your automation operates on infinite board.
  • Not sure if this option will be useful, but you can specify scaling ratio: single integer, setting side of square encoding single pixel. Pixel's color is color of cell dominating by count in it (you can specify 50/50 edge case resolution in your answer). Obviously, in this case side of output area should be proportional to scaling ratio. This option doesn't affect scoring.
  • It's not necessary, but nice to provide either link to online demo or .rle file.

Example result

enter image description here

Decodes to "Hello, world!"

Scoring

Your score is calculated as

score = (initial amount of cells)^2*(number of generations until result) + (number of cells out of output area)*5

Lower score is better.

Happy GoLfing!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ I think this challenge is interesting, although I suggest that the scoring criterion be a combination of the number of initially on cells and the number of generations necessary to get to the final output, without counting the number of on cells in the output (otherwise there's an aspect of QR code golf in the challenge as well, which complicates matters more). Also, I don't really understand the 4th bullet point. Finally, you seem to want to allow different binary cellular automata to compete, just like different languages. Is this true? \$\endgroup\$ Jul 14, 2019 at 22:48
  • \$\begingroup\$ @EriktheOutgolfer Why would including amount of cells out of output area be bad? It only counts cells which aren't part of QR code, so it seems acceptable. 4th point may probably need some illustrations to make it easier to get (or just remove that). You got the last part right. \$\endgroup\$ Jul 14, 2019 at 23:34
  • \$\begingroup\$ Oh, I misread the "out of output" part. So you allow extraneous on cells outside of the QR code with a penalty? \$\endgroup\$ Jul 14, 2019 at 23:36
  • \$\begingroup\$ @EriktheOutgolfer I think that is more or less fine to have some cells on field as long as output in specified area is correct by itself. \$\endgroup\$ Jul 14, 2019 at 23:37
  • 2
    \$\begingroup\$ Could you clarify what classes of automata are eligible? You've specified only binary (two possible cell states). What neighbourhoods are valid? Only the standard 3 by 3 Moore neighbourhood, or also other size and shape neighbourhoods like Von Neumann neighbourhoods? Must all cells in the neighbourhood contribute equally to the outcome (a totalistic automaton) or can different patterns of the same number of "on" cells give different results? \$\endgroup\$ Jul 16, 2019 at 21:06
  • 1
    \$\begingroup\$ Where you choose to draw the line is entirely up to you, but it could have a large effect on the nature of the challenge. For example, if arbitrary size and shape neighbourhoods are allowed, with rulesets based on the arrangement of "on" cells rather than just how many are "on", it may be possible to choose a ruleset that gives the output in a single step (maybe - I haven't thought it through). Whether you see that as a bad thing or an interesting way of solving the challenge will determine how restrictive you choose to be. Personally I'd stop short of allowing quite that much flexibility... \$\endgroup\$ Jul 16, 2019 at 21:09
  • \$\begingroup\$ Is there a standard for QR that avoids all disagreement as to what's a valid code? On further thought, it might be better just to requre a fixed output pattern, like some pixel version of Heelo World, and not have the whole QR layer. \$\endgroup\$
    – xnor
    Jul 16, 2019 at 21:35
  • \$\begingroup\$ In particular, following @xnor's comment, does "decodable to" mean that errors are allowed as long as they're below the threshold for correction? \$\endgroup\$ Jul 17, 2019 at 10:55
3
\$\begingroup\$

How long's left?

Posted here.

\$\endgroup\$
6
  • \$\begingroup\$ Shouldn't the third test case be FifTy Nine MiNutes And ForTy Six SeConds? \$\endgroup\$ Jul 9, 2019 at 19:26
  • \$\begingroup\$ @EriktheOutgolfer Thanks, fixed \$\endgroup\$ Jul 9, 2019 at 19:27
  • \$\begingroup\$ @Shaggy the challenge here isn't to calculate the number of syllables: it's to find the first number that has the same number of syllables as the distance from the current time. \$\endgroup\$ Jul 11, 2019 at 21:14
  • \$\begingroup\$ Ah, OK, I get it now. Yeah, I think that's sufficiently different, so; ignore my previous comment! \$\endgroup\$
    – Shaggy
    Jul 11, 2019 at 21:17
  • \$\begingroup\$ Could you please clarify how many syllable each number has? (A list should help.) \$\endgroup\$
    – tsh
    Jul 12, 2019 at 7:38
  • \$\begingroup\$ @tsh done, see now. \$\endgroup\$ Jul 12, 2019 at 15:05
3
\$\begingroup\$

Character Frequency in a String

Tags:

Posted here.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ i dislike the special case of space \$\endgroup\$
    – Jo King Mod
    Jul 21, 2019 at 1:25
  • \$\begingroup\$ @JoKing If there was no special case for space, a string like 1 a would look something like 1 1; 1;a 1. Also, it's for the challenge. \$\endgroup\$
    – bigyihsuan
    Jul 21, 2019 at 3:19
  • \$\begingroup\$ I'm with @JoKing on this; nothing is added to the challenge by special-casing spaces. \$\endgroup\$
    – Shaggy
    Jul 21, 2019 at 21:08
  • \$\begingroup\$ I'd like to further say that restricting the output this much doesn't seem to add much to this challenge. Why isn't, for example, a list of pairs acceptable? I can't find any justification for your output rules. That's not to say you can't do it, but I have a hard time imagining it will be popular. \$\endgroup\$ Jul 22, 2019 at 18:58
  • \$\begingroup\$ Related. \$\endgroup\$ Jul 23, 2019 at 20:15
  • \$\begingroup\$ @AdmBorkBork, having since given it a try in JS, I'm pretty sure there's a closer (potential) dupe target than that. \$\endgroup\$
    – Shaggy
    Jul 23, 2019 at 22:12
  • 3
    \$\begingroup\$ Having posted this, you should delete the sandbox post. \$\endgroup\$
    – Adám
    Jul 24, 2019 at 6:29
3
\$\begingroup\$

Golf range minimum queries of a list

, , and

Looks like this post hasn't gotten any problems called out, but also not that much support. If you could leave even a brief comment if you don't like it, that would be much appreciated.

(Inspired by the first problem solved in Stanford’s advanced data structures course.)

Despite the academicese-heavy name, the problem we're going to solve is almost unbearably simple.

We have a list of numbers.

[31, 41, 59, 26, 53, 58, 97]

We're going to cut some contiguous snippet out of that list of numbers.

[31, 41, 59, 26, 53, 58, 97]
    |41, 59, 26, 53|

And then we're going to find the minimum of that snippet. In this case, that's quite obviously 26. That's all.

And the obvious solution is pretty fast, too, with O(n) time and O(1) space in the size of the list:

minval = arbitrarily large value
for (i=first snippet index, i<last snippet index, i++)
  if (list[i]<minval) minval = list[i]

So what's with the ?

Where it gets interesting is when you try to see how efficient you can make it when you have a fixed list but a large number of range minimum queries -- snippets to find the minimum of. This version of the problem is useful, for example, if you have a huge time series you want to load only once, but you want to find the minimum of many different subintervals of that time series.

In such a scenario, it would actually be faster in practice to literally precompute all n**2/2 queries, store it in a table, and then just retrieve data from that table for an O(1) time and O(n**2) space solution. Dynamic programming solution from the Stanford slides ^dynamic programming solution taken from the Stanford slides

And then if you're clever enough, you realize that you only have to store each query with size that's a power of two -- you can just combine those power-of-two minima to sum to an arbitrarily sized query, and achieve the same results with constant time and linearithmic rather than quadratic space.

Interestingly, if you keep optimizing, you can get to an O(1) time and O(n) space solution using a sort of augmented list known as a Fischer-Heun structure. I'd love to go into the details of the structure here, but explaining how it weaves into Cartesian tree building on fixed-size snippets would make this question about 50 pages long. It's explained in the Wikipedia page linked in the title (which I've copied here), however, along with several faster-than-linear intermediate structures.

(If you can get past a research paywall, here's the original Fischer & Heun 2011 paper. And if you’d prefer the much more verbose but much more hand-holdy Stanford lecture style, here are the follow-up slides that goes into this solution, including lots of intermediates.)


The challenge

You can either write a full program or a function that calculates the result of a series of range minimum queries given a fixed list. Scoring is set up such that in general, the shortest and most-efficient-over-lots-of-queries code wins.

Input:

A list of integers xs, followed by a series of i, j pairs denoting the start and end of the snippet, inclusive (so the 26 example above uses indices i=1 and j=4). The list of integers is guaranteed to have at least one integer, and 0 <= i <= j < len(xs). This can be taken in any format that works best for your language — for example, one list for xs and one list of tuples for the i, j pairs; or maybe all the different pairs as a variable number of arguments. For a full program that takes in input from stdin, I’ll fix a format for the input:

xs[0] xs[1] xs[2] xs[3] ...
i1 j1
i2 j2
i3 j3
...

Output:

An ordered collection of the range minima for each i, j query, in the same order that they were given. In case an unordered map (such as a Python dictionary) from each i, j query to its range minimum works better for your language, that will also be allowed as an output; as long as it's obvious which minimum is related to which query.

Once again, for a full program that prints to stdout or a file, I’ll fix the format to have each range minimum on each newline (trailing newlines permitted).

Scoring:

Lower score is better; score is determined by

at(b)^2+as(b)

Where b is the byte count of your code, at is the asymptotic runtime Ө(n) of the algorithm in the size of xs interpreted as a function of n, and as is the asymptotic space usage Ө(n) in the size of xs interpreted as a function of n.( All constant coefficients in such Ө(n) expressions must be 1, and only the fastest growing term may be kept in expressions, as is standard.)

Therefore, the above pseudocode solution, which uses Ө(n) time and Ө(1) space, and is 126 characters, would have a score of (b => b**2 + 1)(126)=15876+1=15877. (Of course, the pseudocode isn't really valid since it's missing a construct to deal with multiple queries, and also because it's uncompilable pseudocode...)

Test cases:

Input:

31 41 59 26 53 58 97
1 4
0 2
5 6

Output:

26
31
58

Input:

1
0 0
0 0

Output:

1
1

Input:

-4 28 31 -54
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3

Output:

-4
-4
-4
-4
28
28
-54
31
-54
-54

Sandbox Questions:

  • Would the asymptotic runtime count as a non-observable requirement?

  • is this too long and/or abstruse lol

  • I’m not sure how to word the scoring section to narrow down the most obvious, basic O(n) expression — an algorithm that’s Ө(n) is also Ө(n/16384-50000) by definition. Is what I have clear enough? Have I left any loopholes?

  • I kind of wanted to encourage people to try to implement Fischer-Heun or one of the more time-efficient intermediates in the slides, without restricting them to one particular algorithm (e.g. challenge: you have to make a Fischer-Heun structure). Does the scoring system make sense for this? Is it fair to have, for example, a Jelly answer using the naive algorithm in 3 bytes (score 10) compete with a Jelly answer using the Fischer-Heun structure in 30 bytes (score 31); but a naive Python answer with score 3000+ compete against with a Python Fischer-Heun with score 300?

\$\endgroup\$
1
  • 3
    \$\begingroup\$ [tag:tag-name] \$\endgroup\$
    – Adám
    Jul 30, 2019 at 19:06
3
\$\begingroup\$

Irish Snap: Variant Rules

Introduction

Recently, me and a couple of my friends decided to play some cards, and one of them suggested the game 'Irish Snap', which was the inspiration for this challenge. However, I later learnt that the game has a lot of different rules that work ,some of which are listed here. The rules that are in this challenge aren't currently listed on that page, hence the name, 'Variant Rules'

The Challenge

Given an array of 3 cards, output a truthy or falsey value depending on if they make a valid snap in a game of Irish snap.

Input

The input will be an array of 3 numbers, ranging from 1-13 inclusive, with 11 being jack, 12 being queen and 13 being king. The last number in the array will be the number at the top of the stack of cards.

Rules

The 4 different criteria for if cards make an Irish snap are a snap:

  • The top and middle cards are the same
  • The top and middle cards have a difference of one
  • The top and bottom cards are the same
  • The top and bottom cards have a difference of one

If any of these criteria are met, you must output a truthy value. As well as this, for the two criteria that require the cards to have a difference of one, it 'wraps around', meaning that an ace and a king are considered to have a difference of one, and vice versa.

Test Cases

Input -> Output
1 13 7 -> False
1 4 13 -> True
9 3 6 -> False
8 9 7 -> True
2 6 5 -> True
12 5 11 -> True
10 4 8 -> False
12 13 7 -> False
9 7 10 -> True
7 3 1 -> False
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Wikipedia describes a substantially different game under the same name. Is there any less ambiguous name for this? \$\endgroup\$ Aug 6, 2019 at 8:27
  • 1
    \$\begingroup\$ Although I don't think there is a less ambiguous name for it that I can find, the version I described is a combination of the alternate rules listed below the section you linked: 'conventional snap', 'runs', 'sandwiches' and the last rule I listed is basically a combination of 'runs' and 'sandwiches'. How could I change the name to reflect this? \$\endgroup\$
    – EdgyNerd
    Aug 6, 2019 at 8:38
  • \$\begingroup\$ Should I change the name to "Ultimate Snap", as that's what Wikipedia says those rules are commonly referred to as? \$\endgroup\$
    – EdgyNerd
    Aug 6, 2019 at 8:42
  • 1
    \$\begingroup\$ I think runs as described requires all three cards and in the right order. Maybe "Irish snap: variant rules" would be a suitable title, and the introduction can reference Wikipedia and say that the exact rules we'll be using aren't listed (at time of writing the question). \$\endgroup\$ Aug 6, 2019 at 8:49
  • \$\begingroup\$ Ok, I've added in all of those suggestions \$\endgroup\$
    – EdgyNerd
    Aug 6, 2019 at 11:23
  • 1
    \$\begingroup\$ As our token Irishman, I endorse the keeping of "Irish Snap" in the challenge name! \$\endgroup\$
    – Shaggy
    Aug 7, 2019 at 21:22
  • \$\begingroup\$ Do you think I'll be able to post this now? \$\endgroup\$
    – EdgyNerd
    Aug 20, 2019 at 9:44
3
\$\begingroup\$

Truth Table Composition

Given 2 or more truth tables, output the "shortest" way to compose the first N-1 tables to form the last (Nth) table.

Rules

  • Standard loopholes/io rules apply.
  • Input is a "list" of truth tables
    • A truth table is a "list" of rows that contain the inputs and the corresponding output
      • The input will always be the same length for a given table
      • There must be \$ 2^N \$ rows in a given table, where N is the number of inputs in the table
      • Each row must have distinct input
      • Inputs and outputs must both be "booleany" e.g.:
        • true/false
        • 1/0
        • truthy/falsey
        • "Bob"/"Sally"
    • The input can be in any reasonable format.
      • Any of the formats shown here are reasonable.
      • Taking the output first (ie for &: 1,1,1;0,0,1;0,1,0;0,0,0) is reasonable.
      • Input that requires non-trivial logic to convert is not reasonable.
      • When in doubt, ask in the comments.
  • Output is a "nested structure"
    • Each level of the nest contains information of the:
      • Truth table that was used
      • The ordered inputs (of this structure)
    • If a node is a leaf (one of the inputs to the final truth table) it must:
      • Be distinguishable from the other nodes
      • Contain the index of the input to the final table
    • Output format must be reasonable (see details under input)
  • "Shortest" is measured by the number of nodes in the output structure.
  • It will always be possible to construct the last table with the first N-1.
  • You do not need to handle invalid input.
  • This is , so the answer with the smallest asymptotic time complexity wins! Answers that do not aim to be efficient are also welcomed.

Yes, I'm done with rules now. Sorry.

Test Cases

For these test cases, the output is explained below. Note that this is not the output format you have to use! - $N is the Nnt input to the final table (0-indexed) - N(...) is the Nnt input table applied to ... (also 0-indexed) - Arguments are comma separated and are in this format. - Note that N() is different from $N; the former is the Nnt truth table applied to nothing (only valid in the case of truth tables 1 and 0), and the latter is the Nnt input to the final table.

Input:
(anything)

1 0 0
0 1 1
0 0 0
1 1 1

Output:
$1 (length 1; leaf; gives the second input)
Input:
1 0
0 1

1 1 1
0 0 1
0 1 0
1 0 0

1 0 1
1 1 0
0 0 1
0 1 0

Output:
0($1) (length 2; the first table (not) applied to the second input)
Input:
1 0
0 1

1

0

Output:
0(1()) (length 2; the first table (not) applied to the second table (true))
Input:
0 1
1 0

1

1 0
0 1

Output:
0($0) (length 2; the first table (not) applied to the first input to the final table)
Input:
0 1
1 0

1 1 1
0 1 0
1 0 0
0 0 0

1 1 1
0 1 1
1 0 1
0 0 0

1 1 0
0 1 1
1 0 1
0 0 0

Output:
1(2($0,$1),0(1($0,$1))) (length 8; "(A | B) & !(A & B)")

Meta

I think more test cases are needed, but am unsure what to add.

This is my firstsecond challenge, so all feedback is welcome!

\$\endgroup\$
20
  • \$\begingroup\$ The idea is good, I think. I had trouble understanding at first read though, and didn't understand at all your $ things. I suppose $1 is the same as 1() but I'm not sure. Suggested test case: Input : (1,0;0,1) ; (1) ; (1,0;0,1) with Output : 0() and not 0(1()) or 1(0()). \$\endgroup\$ Aug 13, 2019 at 14:40
  • \$\begingroup\$ @V.Courtois $0 is the first input to the final table, $1, the second etc. 0(...) is the first input table, 1(...) is the second, etc. Any recommendations on a better format? \$\endgroup\$
    – tjjfvi
    Aug 13, 2019 at 14:43
  • \$\begingroup\$ @V.Courtois Added your test case, though 0() is not a valid output as (1,0;0,1) takes in 1 input, not zero, it should be 0($0) \$\endgroup\$
    – tjjfvi
    Aug 13, 2019 at 14:46
  • \$\begingroup\$ Do you mean $0 is the input on the first row of the output table? It got even more foggy... Plus, isn't a truth table's order meaningless? I mean, you even swapped the order of the rows in the last test case. And I just noticed now the # notation... Would you mind clarifying it all? Those signs are nowhere defined in the challenge ^^' \$\endgroup\$ Aug 13, 2019 at 14:52
  • \$\begingroup\$ OH ; and by re-reading all the text I saw that your & is strange: why does 0&0 get 1?? \$\endgroup\$ Aug 13, 2019 at 14:53
  • 1
    \$\begingroup\$ @V.Courtois The "&" is not an &, it is an iff/not xor \$\endgroup\$
    – tjjfvi
    Aug 13, 2019 at 14:54
  • \$\begingroup\$ Oh my bad then, I didn't know for this one. \$\endgroup\$ Aug 13, 2019 at 14:56
  • \$\begingroup\$ @V.Courtois Tomorrow I’ll revise the test case format \$\endgroup\$
    – tjjfvi
    Aug 14, 2019 at 0:38
  • \$\begingroup\$ @V.Courtois I explained & slightly revised the notation; is it clearer now? If you have any suggestions, they would be very welcome. \$\endgroup\$
    – tjjfvi
    Aug 14, 2019 at 12:30
  • \$\begingroup\$ Ah yeah, it looks clearer now. The test case of length 8 is really helpful in the process, too, for guys like me that in general read the test cases before reading what is the actual challenge about :) Let's hear other points of view about this challenge, for my part I don't see any problem now. \$\endgroup\$ Aug 14, 2019 at 12:38
  • 1
    \$\begingroup\$ You can remove the "Exception: if there are 0 inputs, there must be 1 row." line, \$2^0=1\$. \$\endgroup\$ Aug 15, 2019 at 22:16
  • \$\begingroup\$ For languages that support ND array, a ND array (each dimension has size 2) would be a natural representation of a N-ary truth table. \$\endgroup\$
    – DELETE_ME
    Aug 16, 2019 at 4:44
  • \$\begingroup\$ In your example is "1 1 1" = "(1, 1) -> 1" or "1 <- (1, 1)"? \$\endgroup\$
    – DELETE_ME
    Aug 16, 2019 at 4:46
  • \$\begingroup\$ Also: do you know any polynomial time solution to this problem? \$\endgroup\$
    – DELETE_ME
    Aug 16, 2019 at 4:48
  • \$\begingroup\$ @EriktheOutgolfer shame. I'll fix that. \$\endgroup\$
    – tjjfvi
    Aug 16, 2019 at 13:16
3
\$\begingroup\$

Planting Steiner Trees

In the following we are talking about Steiner trees, which are similar to minimal spanning trees: The goal is connecting all nodes via some paths such that the resulting graph that is as short as possible. In contrast to minimal spanning trees when constructing steiner trees you can add additional nodes.

In the following we are talking about points in the real 2d plane and when we are talking about distances and lengths, we are talking about the euclidean distance.

Also, a graph will comprise a set of points where the edges are straight lines between pairs of those points. The length of a graph will be the sum of the length of all edges.

So a steiner tree is a shortest graph connecting all given points possibly with inserting additional points. The following image shows the difference between a minimall spanning tree (blue) and a steiner tree (red).

It is known that it is very difficult to find steiner trees.

enter image description here

Task

Write a program that accepts a list of 2d points and tries to find/approximate a steiner tree of minimal length connecting those points by possibly introducing more points. (It does not have to find the an actual steiner tree.)

The program should output a list of all the points (including coordinates) of the constructed graphs, a list of all edges (including their lengths), the total length of the graph and a graphical representation of the grap.

The program should have a running time of no more than about half a minute for each of the examples on a reasonable computer.

You should also explain how your algorithm works.

Scoring

The program must be evaluated on all the [NOT YET] given test cases. The score is the sum of the total length of all test cases. The lowest score wins.

Test cases

Square:
(0,0),(0,1),(1,1),(1,0)

Nonagon:
(cos(2*pi*a/9),sin(2*pi*a/9)) for a = 0,1,...,8

Ladder:
(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)

Meta: I need to find a good set of test cases. Suggestions are appreciated.

If you have any suggestions, feel free to edit/add. Any improvements of the text are appreciated too.

@El'endia Starman Pointed out some interesting n-gon configurations

\$\endgroup\$
1
  • 3
    \$\begingroup\$ It is known that Steiner trees for regular n-gons where 7 <= n <= 12 are simply the n-gon with one side removed. 4,5,6 all have interesting configurations though. \$\endgroup\$ Oct 31, 2015 at 0:03
3
\$\begingroup\$

Shortest Persistent Object in 5-Char JS

The []+=` subset of JavaScript is known to be Turing-complete. A key part of the construction is obtaining persistent objects whose properties can be set and retrieved in a loop.

Most expressions won't evaluate to constant values. For example, [] != [] when compared by reference. However, some expressions, such as [].name, return the same object every time they are evaluated.

The Task

The following should hold when e is substituted with your submission:

  • (e) instanceof Object (this includes functions and arrays)
  • (e) == (e)

This is , so the shortest valid submission (measured in bytes) wins.

\$\endgroup\$
3
\$\begingroup\$

What's this constructed number's starter?

\$\endgroup\$
7
  • \$\begingroup\$ The confusing part is how you mix single and multiple digit numbers. \$\endgroup\$
    – Beefster
    Sep 3, 2019 at 16:44
  • \$\begingroup\$ @Beefster Could you elaborate on how that confuses you, so that I can try to address it? \$\endgroup\$ Sep 3, 2019 at 17:49
  • 1
    \$\begingroup\$ "A concatenated number is a number that can be built this way through the use of the multiples of single digit numbers: 1,2,3,4,5,6,7,8,9 A.K.A an element in one of these 9 sequences" - I can see the pattern in the example, but this is not very friendly to skimming. Maybe explain what is going on the 3 example? The other thing is that this doesn't really feel like it needs to be limited into multiples of 1 digit numbers. \$\endgroup\$
    – Beefster
    Sep 3, 2019 at 20:47
  • \$\begingroup\$ @Beefster I'll explain through the 3 sequence to make it clearer. It doesn't need to be limited to 1 digit numbers, although that guarantee that no element will ever be in more than 1 sequence, and is just how I decided to write the challenge. \$\endgroup\$ Sep 3, 2019 at 21:17
  • 2
    \$\begingroup\$ I think you might try to find another name (or maybe do not name it at all) for "concatenated number" to avoid the possible confusion of concatenating single and multiple digit numbers. The recurrence is a much clear definition of such sequences and I think that should be put at the very beginning of the description. \$\endgroup\$
    – Joel
    Sep 3, 2019 at 23:13
  • \$\begingroup\$ "Is this clear enough? Is it easily understand what a concatenated number is?" Completely clear imo, although I agree with @Joel: \$10a + b\$ isn't really concatenating, so the title is a bit confusing for multi-digit numbers later on in the sequences. "Any other tag suggestions?" [sequence] maybe? And [integer] perhaps, although probably not; [number] would be enough here, and whether you'd use an [integer] or [string] is up to the user. "Is this a duplicate?" Couldn't find anything like it. "Any further feedback?" Some (large) test cases would be nice. \$\endgroup\$ Sep 4, 2019 at 7:30
  • \$\begingroup\$ @Joel I've changed the name to constructed numbers, as it should avoid any confusion and still makes it easier to refer to numbers that meet the criteria \$\endgroup\$ Sep 4, 2019 at 9:06
3
\$\begingroup\$

43 quintillion permutations

\$\endgroup\$
8
  • \$\begingroup\$ I think the requirement for 1:1 mapping is a bit much. I think it would be much more reasonable to only require that there is at least one numeric representation for every possible permutation and that every whole number corresponds to exactly one permutation. I can't even begin to wrap my mind around a solution that ensures there are no duplicate states on the way up to 43-whatever quintillion, but I can think of a few that could theoretically encode any permutation, but with duplicates in the mapping. \$\endgroup\$
    – Beefster
    Dec 11, 2018 at 22:20
  • \$\begingroup\$ More on "every whole number corresponds to exactly one permutation" - the number of permutations of a rubik's cube requires a minimum of 66 bits to represent, so arbitrary-length integers are already a requirement to implement this challenge, therefore it is totally reasonable to need arbitrarily long integers to represent all permutations. \$\endgroup\$
    – Beefster
    Dec 11, 2018 at 22:23
  • \$\begingroup\$ @Beefster I have been toying with the idea of converting this to a code challenge, where your score is the number of unique permutations you are able to output. \$\endgroup\$ Dec 11, 2018 at 22:51
  • \$\begingroup\$ The issue with that is that it's trivial to cover all the permutations by associating each bit in the binary representation as whether or not to rotate a certain side 1-quarter turn clockwise. The other issue is that it's very difficult to calculate the minimum number needed to represent all permutations for any given algorigthm. I like the idea of making it a code challenge better than code golf, but I can't think of a good criteria either. \$\endgroup\$
    – Beefster
    Dec 11, 2018 at 23:05
  • \$\begingroup\$ I think with a few minor clarifications this would be a great code golf challenge; I think it'd be great to see a non-golfed example program to show how it can be done. Also, as Beefster pointed out, a 64bit int cannot represent all required numbers, does you don't have to worry about the practicalities of actually taking in inputs greater than your language can handle mean I can still use a 64-bit int? Can I use a signed 64-bit int (assuming that makes the code shorter for some reason). \$\endgroup\$
    – Shelvacu
    Aug 19, 2019 at 10:06
  • \$\begingroup\$ Additionally, what are the restrictions on display? Do I have to use the colors WGRBOY? Can I display the cube flipped for some numbers? (W center on bottom, Y center on top, etc) Can I display it rotated? \$\endgroup\$
    – Shelvacu
    Aug 19, 2019 at 10:09
  • \$\begingroup\$ @Shelvacu The idea I'm trying to get across is that due to the potential size of the input, answers don't have to actually perform correctly for each and every input, assuming that the reason why they don't perform correctly is because the input is outside whatever limit the language/type has. So if a Javascript answer works perfectly for all inputs between 1 and 2^53-1, but fails for 2^53 because the input is out of bounds for Javascript, that's completely fine. If it failed for 2^53 because the algorithm used breaks after that many inputs, that's not fine. \$\endgroup\$ Aug 19, 2019 at 10:27
  • \$\begingroup\$ @Shelvacu I'll loosen and clarify the output restrictions in the post itself \$\endgroup\$ Aug 19, 2019 at 10:27
3
\$\begingroup\$

Cleaning the dishes

In this task, you will be given a bar of soap with a width of 1 or more units, which will be inputted as an integer. You will also be given a plate, which you will have to clean, using the soap as few times as you can. The plate will be inputted as a an array of 2 different characters, one of which is the 'dirty' character, and one of which is the 'clean' character. The plate will be at least 1 character. You will have to output an array with the 'clean' character representing the plate, and a third unique character to represent in what positions the bar of soap was placed. None of these 3 unique characters may be whitespace.

How much the soap cleans:

n//2-1 on each side for odd n
n//2-1 on the left side of the soap bar for even n
n//2   on the right side of the soap bar for even n

Input

An integer greater than or equal to 1. A series of 2 unique characters to represent clean portions and dirty portions. Here, '=' represents a dirty portion, and '-' represents a clean portion. '+' represents where the soap was placed.

IN : OUT

3 ===- : -+--
32 ================================ : ---------------+----------------
1 ==== : ++++
5 ----- : -----
4 -====- : --+---
3 -====- : --+-+-
7 === : +--
6 - : -
6 -==-===- : ---+----
5 -==--==- : ---+--+-
3 -==--==- : --+--+--

Rules

  • There are multiple solutions. Any one of them are acceptable, as long as they use the soap the minimum amount of times possible.
  • This is a contest, so the shortest answer in bytes wins!
  • The plate may only be non-whitespace characters, and have 2 unique characters.
  • The soap may only be one non-whitespace character, unique from the other 2 used in the plate.
  • Standard loopholes are not allowed.

Posted: Cleaning the dishes

\$\endgroup\$
4
  • \$\begingroup\$ If "soap input may only contain the characters '0' through '9', and may be multiple characters", then can it not be passed as an integer argument to a function? \$\endgroup\$ Sep 4, 2019 at 4:15
  • 1
    \$\begingroup\$ i already specified rules about soap input in the first paragraph, so i will erase that rule. \$\endgroup\$
    – girobuz
    Sep 4, 2019 at 20:34
  • \$\begingroup\$ There seem to be multiple possible outputs, e.,g.: 3 =-=-= could be either +--+- or -+--+, yes? If that is true, can we output any of them? \$\endgroup\$
    – Chas Brown
    Sep 7, 2019 at 23:34
  • \$\begingroup\$ Yes, any output is acceptable, as long as it works, and is the minimum. \$\endgroup\$
    – girobuz
    Sep 7, 2019 at 23:53
3
\$\begingroup\$

Battleship KotH

This is a pretty rough idea to start but I figured I would drop it in the sandbox so that people can start to think about it and I will remember to do it.

The idea here is a that combines the game, battleship with .

The rough idea is that two enemies would face off, each turn irradiating a location in their opponents source code. Then the opponents source code would be recompiled and then try and attack back.

Some additional thoughts I've had:

  • We will likely want to limit the size of the board to a specific rectangular size

  • I would like there to be a feedback from shooting your opponent (in the game battleship this is hit/miss) so that you are doing more than just firing randomly. Perhaps programs might irradiate a single bit (flipping its value) and get back its value before it was irradiated.

Language choice is a bit tough since I would like something multipurpose and flexible but I don't want to have to deal with the security issues that are involved in compiling and running a fully featured programming language.

\$\endgroup\$
2
  • \$\begingroup\$ radiation-hardening tends to work best with deletion. This is going to need a maximum byte count to be fair, otherwise the best strategy is excessive amounts of whitespace and comments. Love the idea though. \$\endgroup\$
    – Beefster
    Sep 17, 2019 at 14:22
  • \$\begingroup\$ You don't actually have to limit yourself to a specific language on this one. It wouldn't be that hard to use a shell script to run whatever languages are available. One question though: is each program able to read the source code of the other or is each attack supposed to be blind? If you're worried about security, you could run the controller in a docker container or VM. \$\endgroup\$
    – Beefster
    Sep 17, 2019 at 14:26
3
\$\begingroup\$

Injection from two strings to one string

\$\endgroup\$
5
  • \$\begingroup\$ Do you think that a reasonably number of languages won't implement the following: convert the strings into numbers (e.g. treat each character as a base 128 digit) then give a resulting string of those two numbers joined by some other character? I haven't spent too long thinking about it but that seems very short in most languages. I suppose there are other variants though where you map characters to some subset and then join them. \$\endgroup\$ Sep 24, 2019 at 20:42
  • 2
    \$\begingroup\$ @FryAmTheEggman I imagine the solution used is going to depend on the language: what builtins it has, if it's more high-level or low-level, etc. But there may well end up being a prevalent algorithm. \$\endgroup\$ Sep 24, 2019 at 20:57
  • \$\begingroup\$ Why strings? Lists of integers, (even restricted to a range) work as well but don't have the complexities that strings do when it comes to printables etc. I feel like the simpler challenge is going to be the better one. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 26, 2019 at 3:30
  • 1
    \$\begingroup\$ @FryAmTheEggman Don't worry, I've thought of a totally different approach that I think would be shorter for many languages. \$\endgroup\$
    – xnor
    Sep 26, 2019 at 4:46
  • 2
    \$\begingroup\$ @SriotchilismO'Zaic Restricting the character set seems to me like a reasonably simple detail, while making it about strings encourages creativity with string operations, converting to string representations, etc. Also, I personally think string input/output is much more appealing to look at and easier to consume than a list of numbers. \$\endgroup\$ Sep 26, 2019 at 14:38
3
\$\begingroup\$

Code Golf Measurer © 2019

Hexdumps used with xxd look something like this:

00000000: 666f 6f20 6261 7220 7370 616d 2065 6767  foo bar spam egg
00000010: 730a                                     s.

Your task is to convert a hexdump in this form in to the number of bytes used.

Rules:

  • Usual loopholes forbidden.
  • This is , so shortest valid answer in bytes wins.
  • You may or may not include the newline at the end of text (0a). This means that if the hexdump ends in a newline (0a), that input may have it's output reduced by one.
  • An empty input must output 0.

Test cases:

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 2120 4865  Hello, world! He
00000010: 6c6c 6f2c 2077 6f72 6c64 210a            llo, world!.

returns 27 or 26

00000000: 0a                                       .

returns 1 or 0

00000000: 6368 616c 6c65 6e67 650a                 challenge.

returns 10 or 9

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 21         Hello, world!

returns 13


returns 0

Sandbox:

  • Is this clear?
  • Is this a duplicate?
  • Other tags?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Does the extra rule mean that the input can have an optional trailing newline, or that the results in all of your test cases could be reduced by 1? If you mean the former I recommend adding a test case that doesn't end with a newline. If you mean the latter then I recommend explicitly saying the file will end with a newline character. Also I suppose this is a string challenge. Thanks again for using the sandbox :) \$\endgroup\$ Oct 3, 2019 at 20:55
  • \$\begingroup\$ @FryAmTheEggman It means that all test cases could be reduced by one. This was intended as a code golf byte counter, and the newline most certainly isn't usually included. I'll clarify this and add another test case to highlight it. \$\endgroup\$
    – gadzooks02
    Oct 4, 2019 at 15:17
  • \$\begingroup\$ So: discard all the input except the last line, and parse hex? Or just output the last line and claim that your output is in hex? IMO it would be a more interesting problem with xxd input, where the last line is not present. \$\endgroup\$ Oct 5, 2019 at 9:00
  • \$\begingroup\$ @PeterTaylor If I were to switch to xxd, would that be a valid edit, or would that be too big a change such that I would have to post another challenge? \$\endgroup\$
    – gadzooks02
    Oct 5, 2019 at 9:45
  • \$\begingroup\$ I'm sure far more significant edits have been made to sandboxed challenges in the past. \$\endgroup\$ Oct 5, 2019 at 13:10
  • \$\begingroup\$ @PeterTaylor In that case, edited. \$\endgroup\$
    – gadzooks02
    Oct 5, 2019 at 14:52
3
\$\begingroup\$

Java vs C++

Now posted at Time to settle this: Java vs C++

\$\endgroup\$
9
  • \$\begingroup\$ How vital is the validation to the challenge? \$\endgroup\$ Aug 27, 2019 at 21:01
  • \$\begingroup\$ @UnrelatedString I think it's fairly integral if the story is considered. Gotta inform the user that they're feeding you crap. Also it should add an extra element of challenge. \$\endgroup\$ Aug 27, 2019 at 21:07
  • 3
    \$\begingroup\$ @MrRedstoner Validation is generally considered tedious by the users of this site, rather than challenging. I'd recommend reconsidering - clearly the validation code could make use of the submissions as a subroutine. There are also a couple near dupes 1 2 but I haven't found a precise dupe. That said, thanks for using the sandbox! \$\endgroup\$ Aug 28, 2019 at 0:36
  • 1
    \$\begingroup\$ getHTTP would result in... get_h_t_t_p? get_http? Error? Some other thing? \$\endgroup\$
    – Chas Brown
    Aug 28, 2019 at 1:42
  • \$\begingroup\$ @ChasBrown should be get_h_t_t_p, I shall add that. @FryAmTheEggman While I considered it part of the story, if those are the standards I figure I'll remove it and say the validation was done by a previous part of code. \$\endgroup\$ Aug 28, 2019 at 5:24
  • \$\begingroup\$ "If it is neither, output/return a falsey value." I would change this to something like "If it is neither, any unspecified behavior is fine (return a falsey value; give an error; try to convert it somehow anyway; etc.)." As mentioned by @FryAmTheEggman, validation is usually considered a distraction of the actual challenge (and can sometimes even double the code of the program/function for those answering), so most challenges assume the given input will always be valid. Apart from that the entire challenge looks fine, so +1 from me. Thanks for using the Sandbox! :) \$\endgroup\$ Aug 28, 2019 at 9:32
  • \$\begingroup\$ @KevinCruijssen Dang it missed that during the edit. Thanks for telling me! \$\endgroup\$ Aug 28, 2019 at 10:42
  • \$\begingroup\$ What should be returned from an input of a__b (two underscores)? \$\endgroup\$
    – Value Ink
    Aug 29, 2019 at 1:03
  • 1
    \$\begingroup\$ @ValueInk That would be invalid input. 'You may assume all input to be valid'. Therefore I refer you to the ANSI C standard for undefined behaviour. \$\endgroup\$ Aug 29, 2019 at 6:00
3
\$\begingroup\$

Can Jimmy escape the ghosts?

Posted: Can Jimmy escape the ghosts?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ S'all good, no problem \$\endgroup\$
    – Veskah
    Oct 17, 2019 at 14:05
1
17 18
19
20 21
153

You must log in to answer this question.

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