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

4327 Answers 4327

1
63 64
65
66 67
145
1
\$\begingroup\$

Data.List.nub :: Eq a => [a] -> [a]

Tags: , ,


O(n^2). The nub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The name nub means `essence'.) It is a special case of nubBy, which allows the programmer to supply their own equality test.

> nub [1,2,3,4,3,2,1,2,4,3,5]
[1,2,3,4,5]

Goal

If you ever golfed in Haskell and you kind of needed to deduplicate a list, chances are that you chose a different route or were annoyed that there seems to be no solution shorter than importing Data.List.

In this challenge you will write a function [a] -> [a] (unnamed or named) which removes duplicates from a list, the order does not have to be preserved.

Scoring

Since I don't think it's possible to get something shorter than 20 bytes and Haskell sometimes is really annoying to golf with if you want to use lengthy functions, the scoring mechanism will count tokens, please use this program to count the tokens and use the generated template.

  • If your solution is a named function or operator, it must not be defined in another file/module (ie. banning imports).

  • Each solution may impose type constraints, each set of type constraints counts as its own language, compiler flags can be used without any restrictions.

  • Your solution may not assume that the input is non-empty, however if you have an elegant solution which fails on empty input, feel free to include it in your post.

How are tokens counted?

Tokens are counted by using GHC's lexer which you can import Language.Haskell.Extes.Lexer, except that newlines will count as a token too.

White space is ignored, every token of the language will count as one, no matter how long it is so ma >>= f will count as the three tokens ma, >>= and f the same holds true for string or number literals (eg. "abc" or 1.0 each count as 1).

Test cases

[] -> []
[1] -> [1]
[1,1,1] -> [1]
[3,1,1,2] -> [1,2,3]
[1,2,3,3,2,1] -> [1,2,3]
\$\endgroup\$
7
  • 1
    \$\begingroup\$ I think I'm missing something, but what stops the import Data.List;nub solution from winning with score 4? \$\endgroup\$
    – xnor
    Mar 16, 2019 at 1:26
  • 1
    \$\begingroup\$ @xnor: No you didn't, my bad. Fixed, I hope. \$\endgroup\$ Mar 16, 2019 at 2:49
  • 2
    \$\begingroup\$ Hmm, this way it's still no good. Using nubBy (==) is still going to be hard to beat. Guess I need to ban imports completely :( \$\endgroup\$ Mar 16, 2019 at 2:53
  • 2
    \$\begingroup\$ Yeah, I think banning imports is the way to go. I know past token-counting challenges have had "exploits" where the code payload is put into a huge string or number payload, the decompressed and executed by a general-purpose program. I don't see offhand a good way to do that in Haskell without imports though -- do you? \$\endgroup\$
    – xnor
    Mar 16, 2019 at 3:03
  • \$\begingroup\$ I tried writing a solution and the best general-type solution I got is the same as the one I'd use for golfing with imports banned, with 17 tokens. I'm unfortunately not seeing a way to take advantage of long built-ins like the scoring encourages. I see a shorter approach for a restricted type that feels both optimal and hard-to-improve to me. If you don't have some clever better method up your sleeve, I'd suggest a more complex task. Nice token-counting script by way, the number labelling makes it very clear. \$\endgroup\$
    – xnor
    Mar 16, 2019 at 3:36
  • \$\begingroup\$ @xnor: Without imports one could still embed an interpreter, I guess. I was thinking earlier about this and I think there's nothing wrong with counting literals as multiple tokens. However yeah, probably it's best to come up with a more complex task. Thanks for your feedback. \$\endgroup\$ Mar 16, 2019 at 3:59
  • \$\begingroup\$ I don't really see how counting tokens is too much better, and it makes the challenge language specific. \$\endgroup\$
    – dfeuer
    Mar 19, 2019 at 22:26
1
\$\begingroup\$

Make a markdown Table of contents parser

A simple Code Golf challenge in the likes of the Markdown parser.

The parser should ignore normal text and other markup (without an # before it).

Some valid headers are: ### Header 3, # Header1, Text # Header

Sample input:

# Hello
Lorem # Hello2
Hi this is normal text

## This is a subheader
Lorem ipsum

### Subsub
Solor di amet

# Hello again
This is more text!

sample output:

Hello
Hello2
- This is a subheader
--- Subsub
Hello again
\$\endgroup\$
2
  • 1
    \$\begingroup\$ What about ```[linebreak]# text in code[linebreak]```? Or with indentation? What about where there is no space (still formats) : #no space? Or inside quote: > # header/spoiler: >! #header? Please specify these and any other edge cases. \$\endgroup\$
    – Artemis
    Apr 12, 2019 at 15:45
  • 1
    \$\begingroup\$ I'd personally recommend trying to avoid so many edge cases. If you give a precise list of all of the cases that the parser has to care about and then just say something like "ignore any other markup" I think your challenge will be better. \$\endgroup\$ Apr 15, 2019 at 16:10
1
\$\begingroup\$

Growth of the Jackpot (Tentative Name)

(Gauging interest)


There is a money pot that gains $1 for every player currently in the game each turn. At any time, a player can decide to take the money and run or stay in the game hoping for a larger pot. If more than one player decides to leave at the same time, the money will be divided evenly among them, rounded down, with the remainder being put back in the pot. If after 100 rounds, there are still players left in the game, they will split whatever is in the pot at that time. Whoever has the most money at the end of the game wins.

Write a bot to play this game. You will always know the size of the pot, how many players are currently playing, how many were initially in the game, and the current first place amount of money.


On the surface, the optimal strategy is to bail out on turn \$\lceil{100n \over {2n - 1}}\rceil\$ (where \$n\$ is the number of players) because that turn guarantees that nobody can do better than you. But then if everyone does that, they'll split the pot and lose, so the best action to take is not immediately obvious.


One possible variant to round limits would be to have it cost each player $1 per turn they stay in the game, with each player starting with $100 and being forced to take the money and run when they have none left to contribute. Then the game could be run for several rounds.

\$\endgroup\$
3
  • \$\begingroup\$ Kind of a one-shot form of Reaper \$\endgroup\$
    – Veskah
    Apr 17, 2019 at 19:47
  • \$\begingroup\$ I like this. It allows for multiple simple strategies, but has a lot of depth and an interesting metagame aspect. To encourage complicated answers, I would recommend having bots play a few games in a row, to allow a bot to learn optimal timings vs given opponents. \$\endgroup\$
    – MegaTom
    Jun 23, 2019 at 4:59
  • \$\begingroup\$ If a bot may play several games, is the object to win as much money as possible, or to win as many games as possible? \$\endgroup\$
    – Rosie F
    Aug 1, 2019 at 15:08
1
\$\begingroup\$

Hungry Monster 9

My first challenge. Feedback is appreciated.

A monster shaped like 2 is hungry and wants to become a 9. To do so he will eat food, that is shaped like the number 1, seven times.

0000000000
0000100000
0100000000
0000001000
0000020000
0100000000
0000000100
0010000000
0000001000
0000000000

Challenge

It starts with a grid filled with 0, containing the digit 2, and seven times the digit 1. The 2 (aka the monster) needs to move to the closest 1. Upon "eating" the number, 2 will change to 3, and continue to move to the next closest number.

Write a program that outputs the next correct state.

Input specifications

  • The input grid is a rectangle and can be of any size. It doesn't need to be a square.
  • The input can be at any state. For example a grid with a 6 and three times 1 left.
  • The grid will contain exactly one digit higher than or equal to 2 (the "player").
  • The grid will contain seven times or less the number 1.

Rules

  • When the monster gets on the position of where a 1 is, its digit increases by 1.
  • The monsters previous position becomes 0.
  • When the monster is 9, it does not move.
  • The monster can move in 8 directions (horizontally, vertically, diagonally).
  • The monster moves to the closest 1. If there are multiple closest, you may choose any of those. It is not required to be random.

Example Input and Output

This is an example of the first 4 states (and example inputs/outputs):

0000000000
0000100000
0100000000
0000001000
0000020000
0100000000
0000000100
0010000000
0000001000
0000000000
0000000000
0000100000
0100000000
0000003000
0000000000
0100000000
0000000100
0010000000
0000001000
0000000000
0000000000
0000100000
0100030000
0000000000
0000000000
0100000000
0000000100
0010000000
0000001000
0000000000
0000000000
0000400000
0100000000
0000000000
0000000000
0100000000
0000000100
0010000000
0000001000
0000000000

The output is allowed to be an array of lines. ["0000000000", "0100000000", "0000080000"]

\$\endgroup\$
2
  • \$\begingroup\$ If there are multiple closest, it can choose any of those. Does it have to randomly choose, or can it (for example) always take the north-most? \$\endgroup\$ Apr 19, 2019 at 13:27
  • \$\begingroup\$ @AdmBorkBork It does not have to be random. Your example is allowed. Thanks, I'll make that more clear. \$\endgroup\$ Apr 19, 2019 at 16:45
1
\$\begingroup\$

Low diversity quine.

A low diversity quine is a quine (program that outputs it's source code) that uses a low amount of distinct characters.

Scoring:

As a code-golf challenge the program with the lowest score wins.

Score is calculated as: NumberOfDistinctCharacters x ByteCount

Rules:

Standard quine rules apply. Most notably: No source code reading

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Whitespace and brainfuck have a clear advantage :P. Also, the standard quine for a lot of languages is optimal here. Notably V. \$\endgroup\$
    – Beefster
    Apr 20, 2019 at 18:02
  • \$\begingroup\$ Pretty sure we've had (something very close to) this before, but I could be wrong. \$\endgroup\$
    – Shaggy
    Apr 20, 2019 at 23:21
  • \$\begingroup\$ @Shaggy I thought the same, but I'm not so sure anymore. I'm probably confusing it with Eww, those bytes are gross, where answers use the least amount of distinct bytes as well, but when the input contains any of the bytes in your source code, they should remain in the output. So it's related to the source code and distinct bytes, but not a quine. Alternatively I could've confused it with Write a Quine Suite, where answers contain multiple quines that share none of the same characters \$\endgroup\$ Apr 23, 2019 at 15:47
  • 2
    \$\begingroup\$ that uses a low amount of distinct characters usedthat uses a low amount of distinct characters or with a low amount of distinct characters used \$\endgroup\$
    – Artemis
    Apr 23, 2019 at 21:32
1
\$\begingroup\$

Sort a list using a stack and a queue

Consider an unsorted list of length n, containing the integers 1 through n. Your job is to sort them using a stack (FIFO) and a queue (LIFO) and a single register. To do this, you have access to six commands

i    Input the next integer onto the register
o    Output the value of the register
Q    Place the value of the register at the tail of the queue (enqueue)
q    Place the value of the head of the queue in the register (dequeue)
S    Place the value of the register at the top of the stack (push)
s    Place the value of the top of the stack in the register (pop)

A few examples (sorting in ascending order):

Input:
 [1 2 3 4] 
Commands:
 ioioioio

Input:
 [3 2 4 1]
Commands:
 iQiSiQiosoqoqo

Challenge

Write a program or function that, given some (unsorted) list, returns a sequence of commands that outputs an ordered list. However, the number of commands should grow as \$o(n^2)\$, i.e., strictly smaller than \$\mathcal{O}(n^2)\$. That is, for sufficiently large \$n\$, you must always use less than \$cn^2\$ commands (with \$c\$ some positive constant) to sort the list.

  • The input is flexible. The list of size \$n\$ may start from \$0\$ or from \$1\$ and will always contain all integers from \$0\$ to \$n-1\$ or from \$1\$ to \$n\$ respectively. You may take \$n\$ as a separate input if desired.
  • The output is flexible. You may choose a different set of unambiguous command identifiers instead of ioQqSs. You may output as a string (which is allowed to contain superfluous characters such as delimiters, linebreaks, etc), or as an array or list of commands.
  • Your entry must indicate the worst-case output size, e.g., \$\mathcal{O}(n)\$, \$\mathcal{O}(n\log(n))\$, which must of course be strictly smaller than \$\mathcal{O}(n^2)\$.

A few notes:

  • Things like ii, qi, oo should never happen. You only have one register, and overwriting it would mean you can no longer output the full sorted list.
  • A naive approach would be to put the entire input in the queue iQiQiQ... and then cycling through the queue qQqQqQ... until the register contains the next integer in order. However, this approach would mean you have \$\mathcal{O}(n)\$ cycling commands for \$\mathcal{O}(n)\$ numbers, which would be \$\mathcal{O}(n^2)\$ and thus does not meet the complexity requirement.
\$\endgroup\$
13
  • \$\begingroup\$ The restricted-complexity tag means that your code must have a restricted complexity in at least one aspect, not that the output has a restricted growth rate. As it is, I can simply brute force and find the optimal output in all cases, but I don't think that's what you want. \$\endgroup\$ Apr 29, 2019 at 12:28
  • \$\begingroup\$ @EriktheOutgolfer Thanks for raising that point. I'm not sure if brute forcing will always be the shortest in byte count, so I would like to think that different approaches are still competitive. Perhaps I could change it such that the entire algorithm must run in o(n^2) (which would automatically disqualify O(n^2) output)? Or perhaps o(n^2) for the output, O(n^3) for the algorithm. What are your thoughts? \$\endgroup\$
    – Sanchises
    Apr 29, 2019 at 13:04
  • \$\begingroup\$ Unfortunately, most of the time, brute-forcing ends up being the shortest approach. :( Also, yeah, requiring the algorithm to run in o(n^2) but still managing to get O(n^2) output means the answer is... weird. However, the other problem is that your code doesn't know which commands to execute from the beginning, and I'm half-confident that o(n^2) will be enough, but not really confident. I don't think the output can really be o(n). As for the specific complexity, well... no specific opinion yet. :P \$\endgroup\$ Apr 29, 2019 at 13:38
  • \$\begingroup\$ Are you sure this is in \$O(n^2)\$? Something tells me the complexity might be bigger than that when all you have is a stack and a queue. You should also use LaTeX to format your big-O notation: \$O(n)\$ \$O(n \log n)\$ \$O(n^2)\$ \$\endgroup\$
    – Beefster
    Apr 30, 2019 at 0:26
  • \$\begingroup\$ @Beefster Like explained in the notes, you can do this in \$\mathcal{O}(n^2)\$ by just using the queue, but I'll have to check if \$o(n^2)\$ is possible; I'll of course check before posting. Thanks re. MathJax, I forgot this was turned back on. \$\endgroup\$
    – Sanchises
    Apr 30, 2019 at 11:27
  • \$\begingroup\$ I think you need to work out \$c\$- i.e. you should probably put a hard cap on the number of commands. The worst-case naive approach comes out to \$n(n-1) \over 2\$ cycle commands for a total of \$n(n-1) + 2n\$ total commands. You can definitely always do better than that since the naive queue-only approach worst case is a reversed sequence, which is handled trivially by the stack. \$\endgroup\$
    – Beefster
    May 1, 2019 at 19:12
  • \$\begingroup\$ BTW, I came up with the formula by noticing that it is a shrinking queue and you therefore need at most \$l-1\$ cycle commands to get to the correct element from any point in the queue. (where \$l\$ is the queue length) \$\endgroup\$
    – Beefster
    May 1, 2019 at 19:19
  • \$\begingroup\$ Also I think I have the formula off by a bit: It should be \$n(n-1) + 4n\$ since you need \$2n\$ commands for both filling and emptying the queue. \$\endgroup\$
    – Beefster
    May 1, 2019 at 19:21
  • \$\begingroup\$ In addition, skipping the queue for the first element cuts it down to \$(n-1)(n-2) + 4n - 2\$ total commands. \$\endgroup\$
    – Beefster
    May 1, 2019 at 19:25
  • \$\begingroup\$ Following this mental thread, I suggest the following rule: "For any input sequence with length \$n \geq 3\$, you must output fewer than \$n^2 + n\$ commands." \$\endgroup\$
    – Beefster
    May 1, 2019 at 19:40
  • 1
    \$\begingroup\$ Your queues work back to front compared to mine: I enqueue to the tail and dequeue from the head. Perhaps it would be cleanest to just talk about pushing to the queue, popping from the queue, pushing to the stack, and popping from the stack. \$\endgroup\$ May 2, 2019 at 11:28
  • \$\begingroup\$ I'm beginning to suspect that the worst case is linear. For \$4 \le n \le 8\$ the worst case is \$4, 5, \ldots, n, 2, 3, 1\$ at cost \$6n - 10\$. \$\endgroup\$ May 2, 2019 at 13:55
  • \$\begingroup\$ @PeterTaylor I was thinking the same, but I didn't have time yet to verify this. And... have you never heard about left-hand-drive queues? \$\endgroup\$
    – Sanchises
    May 2, 2019 at 15:59
1
\$\begingroup\$

Performance-Based Resource Gathering/Trading

In this KoTH, the goal is to be the bot with the highest amount of money by the end of the game. Bots perform actions to earn money in turns. There are a set number of rounds in a game, and each round allows each bot to play. In a play, bots have set number of milliseconds to run as many turns as possible, growing their crops/trees/animals, mining for materials, or harvesting materials.

Earning Money

There are four basic "professions", though bots are not bound to a specific profession. These professions require land to collect resources, and land is zoned by its owner as one profession:

Farming

Farming uses turns to plant, grow, and harvest crops. There are three crops: wheat, carrot, and cotton. Each unit of land zoned for farming can hold up to 40 crops simultaneously. There is no randomness in farming. The crops are:

  • Wheat: The most basic crop, wheat, takes 40 turns to grow. It is planted with 1 wheat seed, and grows into 2 wheat
  • Carrot: Carrots are the fastest growing crop, taking only 16 turns to grow. Carrots are planted with one carrot, and grow into 4
  • Cotton: Cotton grows very slowly, but is a valuable item in the economy. It is planted with 1 cotton seed, and produces 3 cotton in 96 turns.

Ranching:

Ranching uses land to raise animals, which can be used to produce meat and other goods. Ranching is only very mildly randomized. There are three animals: chickens, cows, and sheep.

  • Chickens: A chicken takes up 2.5% of the land it occupies. Chickens lay eggs once every 8-10 turns, and an egg can be hatched into a chicken in 64 turns. Chickens last 192 turns before they stop producing eggs. Chickens can be harvested for 1 meat
  • Cows: Cows do not produce items until they are harvested. A cow takes up 5% of the land it occupies, and are "mature" 144 turns after being bought. Mature cows can be harvested for 6-8 meat and 2 leather
  • Sheep: A sheep takes up 6.25% of the land they occupy. Sheep last indefinitely, and produce wool every 112-132 turns. They can be sheared for 2 wool each time this happens. Sheep do not produce anything when harvested, and never stop producing wool

Woodcutting:

Land zoned for woodcutting contains 12 spaces for trees. Woodcutting is a moderately random-based profession. There are three types of trees available:

  • Oak: Oak saplings take 120-132 turns to grow, and produce 8-16 wood
  • Cedar: Cedar saplings take 84-96 turns to grow, and produce 5-9 wood
  • Hemlock: Hemlock saplings take 240-280 turns to grow, and produce 14-22 wood

Mining:

Mining is a completely random-based profession. Each turn in which the bot mines produces one of three materials:

  • Stone: Stone has a 65% chance
  • Iron: Iron has a 30% chance
  • Gold: Gold has a 5% chance

Economy/Raw Materials

You may be wondering: What do the bots do with all these materials? Well, factories can be built on land, and used to make new items. These items can be sold to NPC traders, or used by bots to improve their efficiency at a profession.

Wood: Wood is used for the creation of tools, construction of factories, and as a fuel source

Stone: Stone is used for construction and tools

Iron: Iron is used for the creation of tools and factories

Gold: Gold is highly sought after by traders

Wheat: Wheat is necessary to feed cows and sheep, as well as the creation of bread

Carrot: Carrots are necessary to feed chickens

Cotton/Wool/Leather: The Loom factory converts these materials into cloth, which is sold to traders or used to make clothes

Eggs: Eggs are necessary to make bread

Factories

There are three factories, each for a specific type of good:

Loom: The loom converts cotton, wool, and leather into cloth, and cloth into clothes. Clothes increase the amount of time to run turns by 20% per piece equipped, up to 3, for the next 5 rounds.

Bakery: The bakery converts wheat into flour. Flour and eggs are then converted into bread, which can be sold or equipped. When consumed, bread increases time to run turns by 25% for the next 2 rounds. Meat can also be consumed, but increases the time by 40% for 3 rounds.

Smithy: The smithy creates tools. These tools are: plow, trough, axe, and shovel. Each tool doubles the time for ticks in the round it is used.

Other

This is not complete, and many numbers still need to be added or changed to make things more equal between professions. Things like land still need to be figured out, but that's what the sandbox is for I suppose. This seems a little complicated, but each bot will probably stick with either a single profession or just be a factory owner.

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

Dining philosopher problem

This question is motivated by the lack of concurrency related puzzles on PPCG. The goal of this question is to solve the Dining Philosophers Problem.


What is the dining philosophers problem (DPP) ?

The DPP is one of the most famous concurrency problem, used to illustrate what is a deadlock for instance.

n philosophers are dining together at a circular table. Between each philosopher, there is a fork. In order to eat, each philosopher should have two forks (one in each hand).

The problem is that, if all philosophers try to take the fork on their right, then wait until the one on their left (taken by the philosopher on their left) is available, they will wait forever.

Solving the problem is finding a strategy so that no philosopher waits forever.


Your program

Takes an input n, the number of philosophers (and the number of forks). Run n philosophers in parallel, each philosopher output its dining events.

There are 4 different dining events possible:

  1. Philosopher i takes the fork j;
  2. Philosopher i tries to take the fork j, but fails (the fork is already taken);
  3. Philosopher i release the fork j;
  4. Philosopher i eats (and leave the table/release the forks and do not compete anymore).

A trace is correct if:

  • A fork is taken by at most 1 philosopher at any time (between two events 1 for the same j, there must be an event 3 for that j).
  • A philosopher only interacts with neighbourgs forks (in events 1, 2, 3, j is i or (i+1)%n).

The output format is a sequence of events. You can choose how to represent each event, but the following is suggested:

  1. i+j
  2. i!j
  3. i-j
  4. i

A (non-golfed) C version is available here, with output in plain english. Try it online!

Rules

This is . You should, in addition, consider the following points:

  • You must solve the problem concurrently, i.e. create one thread per philosopher and use usual atomic operations. Said otherwise, you should output a trace of an execution, not compute a possible scheduling.
  • You can not rely on time to solve the problem (no such thing as: philosopher 1 waits 1 sec, philosopher 2 waits 2 sec, etc..). To generalise, you can not use the identifier of the philosopher to do something else than finding the neighbourg forks.
  • If you add a TIO link in addition to your code, you can add any thread yield (or equivalent in your language) in the TIO version, in order to emphasize non-determinism.
  • If you add a TIO link in addition to your code, you can add use an extra lock to avoid concurrency artifacts on standard output, on the TIO version. You can not use that lock to solve the problem (i.e. if we remove this lock, the solution must remain correct). In particular, you can use this lock to atomically do an event and output it.

Example: the TIO version of:

try = try_lock(fork_1)
if (try is success)
  output("1+1")
else
  output("1!1")

can be :

lock(output_mutex)
try = try_lock(fork_1)
if (try is success)
  output("1+1")
else
  output("1!1")
unlock(output_mutex)
yield()

Example run

for n = 4, the following are possible outcomes (notice that both are traces generated from the same program, it happened that the scheduling was not the same on both runs):

0+0
0+1
0
0-1
0-0
1+1
1+2
1
1-2
1-1
3+3
3+0
3
3-0
3-3
2+2
2+3
2
2-3
2-2
0+0
2+2
2+3
1+1
1!2
0!1
2
2-3
2-2
1-1
1+1
1+2
1
1-2
1-1
0-0
0+0
0+1
0
0-1
0-0
3+3
3+0
3
3-0
3-3

Questions to be answered:

  • The goal is to have a concurrent implementation of the problem (i.e. the scheduling of events should not be fixed, there should be a thread per philosopher, etc.). How to emphasize that in an understandable manner ?
  • Concurrency leads to problems, such as interleaving in stdout. Here, what I have in mind is that when the philosopher thread takes a fork, it can atomically output it on stdout, in order to reflect what actually happens. Said otherwise, I'd like to propose a way to assume that the output reflects locks behavior. Another problem is that, for small n, the output is likely to be deterministic (thread i finishes before i+1 is even started). Hence I'd like to allow the programmer to add any thread_yield() (or sleep, or anything that introduce non-determinism) to break that.
  • This kind of puzzles, intended to be solve by distributed algorithms, is quite unusual on ppcg. Codegolf is a possible scoring system, but maybe there are better systems (like, the less synchronisation, etc.).
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You have a typo in the introduction: each philosopher should have to forks \$\endgroup\$
    – Artemis
    May 2, 2019 at 14:20
  • 1
    \$\begingroup\$ As a puzzle this isn't interesting: the solution is too well known. Concurrency is of dubious observability: certainly it can't be determined from the output or the timing, because that can equally be done by simulating green threads with a random number generator to select which state machine advances, and that's probably golfier than using semaphores or similar. IMO this isn't a good fit for the site. \$\endgroup\$ May 3, 2019 at 10:05
  • \$\begingroup\$ @PeterTaylor I don't agree with your first argument : ppcg contains a lot of problem which solution is known. Concerning the second part, I agree: not using concurrency probably leads to a shorter code. However, the point of this question is to illustrate that concurrent programming is ignored on ppcg, while it is, in everyday programming, a real problem. That is why, I think, we should find a way to integrate problems based on concurrency. Surely code-golf is not the best rule, but not all problems on ppcg are code-golf (e.g. popularity). We should suitable rules for such programs. \$\endgroup\$
    – Bromind
    May 3, 2019 at 13:32
  • 2
    \$\begingroup\$ (1) Emphasis on "As a puzzle". The presentation of this question seems to me to present it as a puzzle to be solved, and while there are questions like that on this site they tend not to be the best ones. If nothing else, once the first person solves it and posts an answer, everyone else can just copy that answer. (2) PPCG is almost the opposite of real world coding, where clarity is the most important criterion. If you can find a good winning criterion then that's great, but shoehorning a problem into a criterion which doesn't fit is to no-one's advantage. \$\endgroup\$ May 3, 2019 at 17:38
  • 2
    \$\begingroup\$ I don't know much about concurrency, so I'll comment from the view of a general site member. It's weird to me that we're printing the trace which is easy to generate non-concurrently, with the hard-to-define requirement of it being generated concurrently buried underneath. I think it would make more sense for our code to implement each of the philosophers, under the requirement that simulating philosophers all running our code results them in all eating. This would mean explicitly specifying what input each philosopher gets at each step and what they can do, in a way that forces concurrency. \$\endgroup\$
    – xnor
    May 3, 2019 at 22:09
1
\$\begingroup\$

Given a position of a chess piece and another square, determine if the chess piece attacks that square

Input

Input would be in the form

Qe4 c6

Where the first term denotes the piece and its position and the second term is the square we're interested in.

Labels for pieces are:
K - king
Q - queen
R - rook
B - bishop
N - knight
P or empty - pawn

In fact, the input could be left to be decided by the programmer, to make them creative in coming up with the most efficient input method, for example any of these could be valid, if the programmer decides so:

Qe4, c6
[Qe4, c6]
Qe4c6
qe4-c6

Even the order could be reversed if that makes parsing easier. Basically the input could be left completely to the programmer's liberty.

Output

So in the above case the input

Qe4 c6

would give an output

True

Because the queen on e4 indeed attacks c6. Outputs like 1 or any other boolean outputs would also be allowed.

An input like

Nc3 a3

would produce

False

because a knight on c3 doesn't attack a square on a3.

Possible problems

There are some invalid inputs possible, like:
1. Wrong letter for a piece, like "Te2"
2. The coordinates which don't exist, like "k9"
3. The second square being the position of the piece itself, for example "Qa3 a3"

Should this be included in the rules or better not to not make it too complicated?

\$\endgroup\$
1
  • \$\begingroup\$ At least for code golf, all inputs are assumed valid because adding input validation tends to inflate scores significantly. \$\endgroup\$ May 28, 2019 at 17:35
1
\$\begingroup\$

Randomly produce a (name of a language) source file that is possibly a quine

Write code in any language that randomly generate a (name of a language) (Java?) source file, meeting the two criteria:

  • It must always (with probability 1) compile successfully in a (language) compiler and version of your choice.
  • It must have non-zero probability to be a quine in (language).

You don't have to make it able to generate all possible programs, and the probability doesn't have to be uniform. The objective is to write a generator shorter than the shortest possible quine in (language) compressed. Technically your code could be deterministic and generate only one program, that is a quine. But it isn't supposed to be competitive.

Your code must not have the potential to damage the computer. But it doesn't matter what the generated (language) program does when it is not the quine that qualifies your answer.

(Restrictions about compiler flags to be added.)

You could either use the built-in random functions and assume they generate true random numbers, or request random information from the input (details to be added). Your code only need to have probability 1 to terminate.

Shortest code wins.


Possible rule

You may not call any (language) compiler or anything else that could check (language) syntax.


I was thinking about C++, but there are short patterns to execute any binary machine code. The language should also have a verbose structure, and not a too short quine.

Candidates: Java, Haskell, Shakespeare Programming Language, Mornington Crescent, SQL, ferNANDo.

Or: Generate a PNG file that is possibly this image. But that may depend to much on a PNG library, and the other part is trivial.

\$\endgroup\$
9
  • \$\begingroup\$ @trichoplax The objective is to write a generator (in any language) shorter than the shortest possible quine (in a specific target language) compressed. \$\endgroup\$
    – jimmy23013
    May 26, 2019 at 8:26
  • \$\begingroup\$ @trichoplax Yes, unless we argue about the case that is possible but has probability 0 to not terminate. \$\endgroup\$
    – jimmy23013
    May 26, 2019 at 8:58
  • \$\begingroup\$ Do I understand it correctly that we can print a normal-ish quine, but with all its strings replaced with random strings without quotes, newlines and other offending characters? \$\endgroup\$ May 26, 2019 at 9:15
  • \$\begingroup\$ As of currently, yes. I hope there are better solutions, but I'm worrying about that this is actually the best solution, and makes it trivial. \$\endgroup\$
    – jimmy23013
    May 26, 2019 at 9:18
  • \$\begingroup\$ Is it possible to somehow restrict a Java program from destroying the computer with a finite amount of code? If so, generating all strings, trying to compile them and running them parallelly until any happens to be a quine might or might not be even shorter. \$\endgroup\$ May 26, 2019 at 9:22
  • \$\begingroup\$ @someone The generator should not destroy the computer. But as of currently it doesn't disallow trying all strings. Maybe I'll forbid calling the Java compiler or syntax checker. \$\endgroup\$
    – jimmy23013
    May 26, 2019 at 9:29
  • \$\begingroup\$ Curiously, this seems similar in concept to Solve Subset-Sum in polynomial time (…if P = NP). \$\endgroup\$
    – xnor
    May 27, 2019 at 2:38
  • 1
    \$\begingroup\$ I'm actually having trouble imagining how to beat a hardcoded quine. Generating nontrivial valid code seems hard. Maybe I'm missing something. \$\endgroup\$
    – xnor
    May 27, 2019 at 2:43
  • \$\begingroup\$ @xnor I think hardcoding a quine except for a string is most likely going to win. So I'm looking for a language that potentially allows more approaches. I may also change it to generate a program for a task other than quine. \$\endgroup\$
    – jimmy23013
    May 27, 2019 at 2:54
1
\$\begingroup\$

Finding distinct road sections

I was recently working on a grid-based road procedural generator, and thought of a neat idea for a new challenge:

The Task

Given a square (equal width and height) 2d array in which each item is one of 2 distinct values (of your choice): grass and road (I will use _ and # in examples), output the grid modified such that each distinct segment of road tiles has had its values changed to a unique value.

Two road tiles are considered to be part of the same segment if they neighbor each other in at least 1 cardinal directions.
Diagonal neighbors are not considered to be part of the same segment (unless they are connected cardinally elsewhere)
A single road tile with no connections is considered to be its own distinct segment.

You may choose the 2 input values used, and all output values used.
"Grass" tiles must remain unchanged.

You may assume there will always be at least 1 road segment, and that the array dimensions will be no larger than 64 by 64

Example:

Input:

___#__######____
_###__#_#_______
___#_##_########
___#____________
####_#######__##
_#_#_#__________
_#_#_#______####
___#_#__________
##_#_##_________
______#_________
_______#_#######
______##________
__###_#_______##
_##_____________
__#######_______
__#_____________

_ is "grass" and # is "road"

Output:

___3__111111____
_333__1_1_______
___3_11_11111111
___3____________
3333_4444444__22
_3_3_4__________
_3_3_4______5555
___3_4__________
66_3_44_________
______4_________
_______7_8888888
______77________
__000_7_______99
_00_____________
__0000000_______
__0_____________

Scoring

This is so fewest bytes in each language wins

Test cases

TBA

Sandbox

  • I feel like the task is poorly worded, but can't think of a better way to word it.
\$\endgroup\$
4
  • \$\begingroup\$ This seems really familiar, but I can't seem to find a dupe... \$\endgroup\$ May 30, 2019 at 19:55
  • \$\begingroup\$ I'm worried about the numbering - is there a defined numbering scheme? The way you have it, it starts from the bottom left and reads to top right. But most (read: ALL) programming languages read from top left to bottom right. \$\endgroup\$ Jun 6, 2019 at 1:14
  • \$\begingroup\$ I would specify either the numbering relation, or that it doesn't matter. \$\endgroup\$ Jun 6, 2019 at 1:14
  • \$\begingroup\$ @mackycheese21 You may choose the 2 input values used, and all output values used. \$\endgroup\$
    – Mayube
    Jun 6, 2019 at 2:10
1
\$\begingroup\$

Draw a regular prism

Input

The input is a single integer i between 3 and 8.

Output

The image of a regular prism with the two regular polygonal faces having i edges each. For example, if i=3 your code should draw a triangular prism using two equilateral triangles.

Rules

The diameter of the polygonal (i.e. triangular if i=3) faces must be at least 200 pixels as should the distance between the regular faces. You can show the image at any angle you like as long as at least two faces of the prism are visible, including one of the two regular polygonal faces.

The edges of the prism that are visible should be in black and the edges that are not visible should be drawn with dotted black lines, a dotted line being a line where in at least 3 distinct, non-connected places (meaning separated by black) there's an absence of black color.

Examples

enter image description here

enter image description here

enter image description here

\$\endgroup\$
2
  • \$\begingroup\$ You have your examples with the bases aligned. Is that required for output? \$\endgroup\$ May 30, 2019 at 19:35
  • \$\begingroup\$ @AdmBorkBork No. Unless you think it should be? \$\endgroup\$
    – user9207
    May 30, 2019 at 20:29
1
\$\begingroup\$

Moved to Make Gimbap cutter

\$\endgroup\$
10
  • \$\begingroup\$ I don't understand how your last test case follows your rules (and other test cases), since I only see two valid Gimbap, @) and @))) in the input. \$\endgroup\$ Jun 7, 2019 at 12:55
  • \$\begingroup\$ @AdmBorkBork There is two valid Gimbap, @) and @))), than split them to @) and @) @) @). So output is @) @) @) @). I'm not that good at English, though. Can you suggest me the way to make question clearer? \$\endgroup\$
    – LegenDUST
    Jun 7, 2019 at 13:01
  • \$\begingroup\$ Oh, so the output is only the valid Gimbap? That makes more sense. Will the input ever contain anything other than @ or )? I would recommend it doesn't. \$\endgroup\$ Jun 7, 2019 at 13:04
  • \$\begingroup\$ @AdmBorkBork Input is made with only @ and ). \$\endgroup\$
    – LegenDUST
    Jun 7, 2019 at 13:06
  • \$\begingroup\$ Would )))@) be a valid input? \$\endgroup\$ Jun 7, 2019 at 20:43
  • \$\begingroup\$ @LuisfelipeDejesusMunoz It would. Then output will be @). I'll add that to example. \$\endgroup\$
    – LegenDUST
    Jun 8, 2019 at 4:14
  • \$\begingroup\$ So in other words: count all )s which occur after the first @ and output that many @) separated by spaces? \$\endgroup\$ Jun 12, 2019 at 13:51
  • \$\begingroup\$ @PeterTaylor Yup. But I moved it into main site. \$\endgroup\$
    – LegenDUST
    Jun 12, 2019 at 13:56
  • \$\begingroup\$ When you do that you should edit the sandbox post to just be a link to the question on the main site, and then delete it, as described in the second paragraph at the top of this page. \$\endgroup\$ Jun 12, 2019 at 14:11
  • \$\begingroup\$ @PeterTaylor Thanks you. I'll edit my posts. \$\endgroup\$
    – LegenDUST
    Jun 13, 2019 at 5:37
1
\$\begingroup\$

Draw an Image on the screen efficiently

Imagine you have a special rectangular screen made of square pixels. It consists of \$n\$ rows and \$m\$ columns. For every row and every column there is one swich (so \$n + m\$ switches in total). To turn a certain pixel on - let's say at position \$(i,j)\$ - we can press switch \$i\$ (of the row switches) and switch \$j\$ (of the column switches) at the same time.

As soon as some pixel has been turned on, it stays on, even if we press the same combination of switches again. META: Is this a good idea? Or should we say that each pixel should be turned on exactly once and may not be activated again?

But we can also press an arbitrary number of switches at the same time: Lets say we press switches \$0,2,3\$ of the row switches and \$1,5\$ of the column switches, then all the pixels \$(i,j)\$ with \$i \in \{0,2,3\}\$ and \$j \in \{1,5\}\$ will get turned on, so all the pixels \$(0,1),(0,5),(2,1),(2,5),(3,1),(3,5)\$.

If we now want to draw a picture on the screen you could do that pixel for pixel, and we'd need \$n \cdot m\$ actions in the worst case - that is, when we have to turn on every pixel. But as we can press an arbitrary number of switches at the same time, we can do better than that. We can for example do row by row: This means we select one switch for the current row, and all necessary column switches to activate all the pixels we need for this row, so in total we would need \$\min\{n,m\}\$ actions. But can we do better than that?

The task is now to write a program that given some black and white image computes a shortest sequence of actions (=simultaneous switch activations) that turns on exactly all the white pixels of the given image.

Details

  • You can also take a matrix/list of lists as input, or a list of the coordinates of the active pixels.
  • You can additionally take the size \$(n,m)\$ as an input (or \$(n-1,m-1)\$ if you prefer.
  • The output is also flexible: You can represent every action as a list of two lists with the corresponding indices of the switches where each of the indices are in \$\{0,1,\ldots,n-1\}\$ or \$\{0,1,\ldots,m-1\}\$ respectively (or also 1-based indexing is fine), or alternatively you enumreate all switches as \$\{0,1,2,\ldots,n+m-1\}\$ and use just one list to represent this action.

    Alternatively you can also just use lists of size \$n\$ and \$m\$ (or one of size \$m+n\$) with truthy and falsey values representing the switches that get activated.

Related: Matrices Generated Using Rectangles

\$\endgroup\$
4
  • 1
    \$\begingroup\$ It may be worth clarifying that the switches don't stay on after an action (i.e. we don't spend actions deactivating them). I'm not sure if it was the use of the word "switch" over "button" that made me think this would be the case but it may be worth running it past some other people. \$\endgroup\$ Jun 4, 2019 at 19:07
  • \$\begingroup\$ @FryAmTheEggman Thanks a lot for the effort of going through this draft! Is "button" used more for switched that just make a momentary contact? To be honest the alternative challenge that include also switching off the switches would maybe be even more interesting! \$\endgroup\$
    – flawr
    Jun 4, 2019 at 19:19
  • \$\begingroup\$ There are probably quite a few variations of this that would be fun (I'm still thinking about your meta question)! In any case, where I live I think that is the case in that most people would say my laptop has a power button, but the room I'm in has lights controlled by a switch. \$\endgroup\$ Jun 4, 2019 at 19:27
  • \$\begingroup\$ Maybe add restricted-complexity, if this is even possible in polynomial time? \$\endgroup\$
    – lirtosiast
    Jun 16, 2019 at 8:05
1
\$\begingroup\$

Cumbersome IO format

The cops' task is to write a program in language A to solve (task about integer lists 1) and a program in language B to solve (task about integer lists 2). The second program must be able to use the output of the first program.

Others could golf your programs. Highest (C + total length of your programs) / (C + minimum total length of the programs without the restriction) wins. (C is a fixed constant to be chosen.)

(Details to be written. The format would be similar to The Bowlers-Golfers Fraction War. Minimum lengths of the two parts would be taken from other challenges.)

\$\endgroup\$
2
  • \$\begingroup\$ Would a pair of languages that both implicitly eval input and uneval output (and since it's a integer list, pretty much all golfing languages I know of work like that for lists) work as a optimal (besides the program itself) solution? What does "program length" in the score formula stand for? The score seems to always be 1 to me. \$\endgroup\$ Jun 13, 2019 at 15:17
  • \$\begingroup\$ @someone Highest score wins. This is a bowling challenge to find two languages which work the worst with the other one's IO format. But I think this may not work well, as there isn't much to do after you finds the languages. \$\endgroup\$
    – jimmy23013
    Jun 13, 2019 at 16:40
1
\$\begingroup\$

Moved here

\$\endgroup\$
1
  • 3
    \$\begingroup\$ It would be good to include the words "diameter" and "graph". I don't think this particular graph statistic has been the subject of a question before, but it could well come up again in the future and then those search terms would make it easier to use this as a dupe target. \$\endgroup\$ Jun 19, 2019 at 11:53
1
\$\begingroup\$

Digit Sum of Sum of Digit Sums

Input: An integer from 1 to 1000 (known as N) Expected behavior: The code will go through the first N integers, and work out the digit sum for each integer, the code will then take these digit sums and add these together. The code will then take this total and work out the digit sum for that number. The final number is the expected output.

Example 1:

Input: 12

Output: 6

Behavior:

1) Numbers
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
2) Digit Sums
1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3
3) Sum of Digit Sums
51
4) Digit Sum of Sum of Digit Sums
6

Example 2:

Input: 20

Output: 3

Behavior:

1) Numbers
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
2) Digit Sums
1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2
3) Sum of Digit Sums
102
4) Digit Sum of Sum of Digit Sums
3

There are no restrictions on language type as long as the standard loopholes are avoided. Please demonstrate your code using the last three digits of your current reputation score.

This is code-golf, the shortest number of characters in code will be deemed the winner. In the event of a tie, the one with highest popular answer will be crowned the winner. If both answers are tied in terms of popularity and size, a fight to the death will be used to declare the winner (just kidding...)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Why would anyone want to do this? Motivation is part of a good question. \$\endgroup\$ Jun 20, 2019 at 8:01
1
\$\begingroup\$

Introduction

When dealing with data in two dimensions, data scientists looove to see straight lines emerge, as they can use a simple linear regression to model it - meaning we assume it is in the form of y=mx+b, and all that's left is to find the best m and b to describe the data.

There are several ways to fit a line to any data (I saw there was a challenge with Ordinary Least Squares once), however one of the most flexible one is gradient descent.

When given vectors X and Y, we start with an initial guess of m and b, then iteratively update them, and hopefully we get a better fit when we're done.

We give a "grade" to our current fitted line with mse (the lower the grade - the better the fit):

loss = mean((y - (m * x + b)) ** 2 for x, y in zip(X, Y))

And in each iteration we change m and b using the gradient of that same grade:

b -= 2 * alpha * mean((m * x + b) - y for x, y in zip(X, Y))
m -= 2 * alpha * mean(((m * x + b) - y) * x for x, y in zip(X, Y))

Here alpha is the learning rate (usually smaller than 1), used to keep the steps small enough to advance towards the minimum grade, rather than overstepping it.

The last question asked is when should we stop these iterations. We (a bit arbitrarily) impose two conditions:

  1. The absolute relative change in the grade between two iterations abs(grade1 - grade2)/grade1 is changed by less than some given epsilon, and/or
  2. A given number of iterations N has been performed already.

p.s. I started by assuming the data is just y(x), however this method may be easily extended to an arbitrary number of free variables and one dependent variable.

Challenge

Write a program that accepts inputs: X, Y, m, b, epsilon, N and returns the updated m and updated b after performing gradient descent as described.

corner cases:

  • X and Y may be empty, in which case m and b are returned unchanged.

This is code golf, so shortest code in bytes wins.

\$\endgroup\$
2
  • \$\begingroup\$ This is in need of a woked example and a fee test cases. \$\endgroup\$
    – Shaggy
    Jun 22, 2019 at 22:17
  • 1
    \$\begingroup\$ What does mean mean? What does zip mean? Those should be made clear, just like you made alpha clear. \$\endgroup\$ Jun 25, 2019 at 12:44
1
\$\begingroup\$

Proposed alternative to this

Golf an H interpreter

H is a text-based, weakly-typed string concatenation language. You task is to run an H script. You may do so by creating an interpreter, a compiler, a transpiler, or by any other reasonable means.

Definitions

Anything not defined herein is undefined behaviour and your implementation does neither have to support it nor does it need to throw an error. This includes unmatched quotes, invalid escapes, usage of variables before definition, etc. All given H scripts will abide by all the rules as stated.

General H syntax

Scripts: One or more lines, each containing zero or more statements, optionally followed by a comment.

White-space: you only have to support spaces in strings (tabs are escaped), plus tabs and/or spaces leading up to a comment.

Operators: There's only one, +, which is string concatenation.

Comments begin with # and continue until the end of the line. # may be prefixed by one or more spaces and/or tabs.

name: a sequence of exactly 4 single-case ASCII letters [A-Z] or [a-z] (you decide the scheme)

value: a +-delimited sequence of one or more strings (see below) and/or previously defined names. The combined value will never exceed 1000 characters.

Strings

Opened and closed by " and support ASCII 32–126 but with the following escape sequences:

\\: the literal backslash character; \

\n: a line break; CR, LF, CRLF, or LFCR (you decide)

\": a quotes symbol; "

\t: a tab character; (HT) or 2, 4, or 8 spaces (you decide)

A string matching the regex 0|-?[1-9]\d?\d? (i.e. look like an integer) may be left unquoted.

Statements

Terminated by ; but may not span multiple lines. There are only three types of H statements:

def name=value; sets the variable name to the given value.

print(value); prints value without trailing line break.

input(value;name); prints value without trailing line break, allows the user to enter a sequence of characters that extend that line, and assigns the characters to name. Any subsequent output begins on the next line.

Test script

The following assumes you have decided on the uppercase variable name scheme:

def HELO="Hello, ";
def HSMO=HELO+"strange"+-1;print("");
input(HSMO+"what is your name?";NAME);         #enter "User A" via stdin
#print(-123)   # nope
print(HELO+"\""+NAME+"\"\n\tthis isn't APL\\"+360+"!");

#done
print(-12+34)	# note the tab before #

Here is the equivalent using a lowercase variable name scheme:

def helo="Hello, ";
def hsmo=helo+"strange"+-1;print("");
input(hsmo+"what is your name?";name);         #enter "User A" via stdin
#print(-123)   # nope
print(helo+"\""+name+"\"\n\tthis isn't APL\\"+360+"!");

#done
print(-12+34)	# note the tab before #

Running the appropriate script, and entering User A should, according to the scheme where \t means ASCII 9 (HT), leave the console/screen/window showing:

Hello, strange-1what is your name?User A
Hello, "User A"
	this isn't APL\360!-1234

If instead you decided that \t means four spaces, it should show:

Hello, strange-1what is your name?User A
Hello, "User A"
    this isn't APL\360!-1234

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You may want to explicitly state that User A is the STDIN-input in the Test script. I must admit I just can't read and read past the explanation of input(value;name); when going through the test script and was thinking: where is def name="User A";. And based on "Anything not defined herein is undefined behaviour and your implementation does neither have to support it nor does it need to throw an error." we can assume all scripts are valid, so no " that are unmatched, and no variable used before it is defined, and stuff like that? \$\endgroup\$ Jun 28, 2019 at 13:45
  • 1
    \$\begingroup\$ @KevinCruijssen How is it now? \$\endgroup\$
    – Adám
    Jun 28, 2019 at 15:50
  • 1
    \$\begingroup\$ Perfect. :) I had already upvoted I see. Everything is clear to me now. \$\endgroup\$ Jun 28, 2019 at 16:40
  • 1
    \$\begingroup\$ @UserA No. There is an overwhelming consensus that one should avoid bonuses in code golf. \$\endgroup\$
    – Adám
    Jul 3, 2019 at 13:23
  • 1
    \$\begingroup\$ @UserA It is very probably that many of the solutions will allow all of those any way. \$\endgroup\$
    – Adám
    Jul 3, 2019 at 13:24
1
\$\begingroup\$

Switch the colour of the largest non-unique connected shape

Given a rectangular grid of square cells, find the non-unique connected shapes with the largest area, and switch their colour

Input

  • A rectangular grid of cells, each of which has 1 of 2 distinct values ("colours")
  • You can choose to accept any of
    • an image with only 2 distinct pixel colours
    • text with only 2 distinct characters (also allowing newlines for forming a rectangle)
    • a 2d array, with each element having 1 of 2 distinct values
    • a 1d array, plus a width and/or height

The 2 distinct values will be referred to as "colours", but the rules apply similarly for all of the permitted formats

Output

  • A rectangular grid of cells in the same format as the input, using the same 2 colours
  • For each shape required to be changed, all of its cells have been switched to the other colour

Rules

  • Each cell is part of a connected shape, which contains all cells of the same colour that can be reached by a path made up only of vertical or horizontal steps to adjacent cells of the same colour (no diagonal steps)
  • The grid does not wrap: a shape cannot be connected across the outer boundary
  • A shape is identical to another if it can be made to coincide exactly with it by any combination of
    • translation
    • rotation by an integer multiple of 90 degrees
    • reflection in any vertical or horizontal line
    • switching its colour
  • A shape is unique if no other shape is identical to it
  • The area of a shape is the number of cells it contains
  • The shapes to be changed are those with the largest area, of those that are non-unique
  • If 2 or more distinct shapes are non-unique and have the largest area, all instances of each distinct shape must be changed
  • If there are no non-unique shapes, the output is the same as the input
  • A grid (input or output) may sometimes contain only 1 of the 2 colours

Test cases

Each test case is an input followed by its unique correct output

.  .

..  ..

.#  #.

.#  .#
..  ..

.#  #.
#.  .#

..#  ...
...  ...
.#.  ...

.......  .......
##.....  .......
#.....#  .......
.....##  .......

....##.  ....##.
##..##.  ....##.
#.....#  .......
.....##  .......

#.....###.  ..........
#.......#.  ..........
##...##...  ..........
.....##...  ..........
##........  ..........
##..####..  ....####..

.......###  .......###
..##..####  ......####
..#..###.#  .....#####
....###..#  ....######
...#######  ...#######

.......###  #######...
.##...####  ######....
.#...###.#  #####.....
....###..#  ####......
...#######  ###.......

........####  ########....
.###...#...#  ########....
.#..#.#.##.#  ##..##..##..
.###.###...#  ####........
....########  ####........

........####  ########....
.###...#...#  ########....
.#..#.#....#  ##..##......
.###.###...#  ####........
....########  ####........

The same test cases with colour coding for human reading (click image for larger version):

test cases with colour coding

Scoring

This is . Your score is the number of bytes in your source code. For each language, the code with the lowest score wins


Sandbox thoughts

  • Any important/useful test cases welcome
  • Is there a more useful format for 2d test cases?
  • Are there 2 distinct characters that would make human reading easier?
  • Is this a duplicate?
  • Can anything be made clearer or more succinct?
  • I'm also trying to think of a better name
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think using "remove" and "change" to mean the same thing is confusing. If I understand correctly, "removing" means to change the colour of, right? That wasn't very intuitive to me on my first reading. \$\endgroup\$ Jun 29, 2019 at 16:52
  • \$\begingroup\$ Ah good point. Thank you. I will try and make that consistent throughout \$\endgroup\$ Jun 29, 2019 at 19:16
1
\$\begingroup\$

Some enchanted avening

(you may see a stranger across a crowded room).

This is one part of a multi-part series inspired by various built-ins in R. Credit goes to digEmAll for suggesting this one.

ave calculates particular grouped values of a list.

For example, we would group x in the following way based on the criteria given in f:

x = [2, 1, 3, 5, 4, 1, 5, 5]
f = [[1, 2, 2, 2, 1, 2, 1, 1], [1, 1, 2, 2, 2, 1, 1, 2]]

     x f1 f2
[1,] 2  1  1    -> group [1,1]
[2,] 1  2  1    -> group [2,1]
[3,] 3  2  2    -> group [2,2]
[4,] 5  2  2    -> group [2,2]
[5,] 4  1  2    -> group [1,2]
[6,] 1  2  1    -> group [2,1]
[7,] 5  1  1    -> group [1,1]
[8,] 5  1  2    -> group [1,2]

Then for each group, we apply a given function (in R, the default is mean), let's say sum:

group [1,1]: 2, 5 -> sum = 7
group [2,1]: 1, 1 -> sum = 2
group [2,2]: 3, 5 -> sum = 8
group [1,2]: 4, 5 -> sum = 9

Then we replace each value in the group by the group sum, resulting in an output of:

[7, 2, 8, 8, 9, 2, 7, 9]

Inputs:

  • a list x of integers
  • a list of lists f or an arbitrary number of lists, each of length equal to x; these are the factors to group on
  • a black-box function FUN that takes a list of integers and returns a single integer value

Output

  • a list o of length equal to x where each element o[i] is equal to FUN(group(x[i])), or as the documentation says:

    A numeric vector, say y of length length(x). If f is g1, g2, e.g., y[i] is equal to FUN(x[j], for all j with g1[j] == g1[i] and g2[j] == g2[i]).

Rules

  • Input can be in any order and in many flexible output formats.
  • You may assume that the outputs will always result in integers.
  • If your language has a builtin for this for some reason, please also implement your own solution.

Sandbox questions/notes:

  • I've done two of these so far and found a reference to a musical that is somewhat appropriate, any suggestion is appreciated there.
  • Need to add test cases
  • Need to work a bit harder on the explanation of how ave works.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could call this something along the lines of "Ave Maria von Trapp"? Aside from that I understood your description well enough to write a (poor) answer. \$\endgroup\$ Jun 26, 2019 at 19:45
1
\$\begingroup\$

Manage a todo list using Cypher (WIP)

Introduction

A list is a common, well-understood data structure. Neo4j's property graph model can represent any data structure. Using the Cypher query language, write a collection of statements for managing a todolist

Challenge

Manage a todo list using parameterized Cypher.

Todo list items are composed of two pieces of information:

  • todo:string - the textual content describing the thing to do
  • completed:boolean - whether this todo has been done

Todo list operations:

  • add new, view, edit, remove, complete, un-complete individual todo list item
  • re-order todo list item
  • view all items
  • view all completed items
  • view all "active" items (items not yet completed)
  • complete all todo list items

Considerations:

  • empty todo list

Out of scope:

  • multiple lists

Answer Format

For each operation, provide a code block of Cypher. Identify the operation with its description. Separate each operation with a --- line. Like this...

  1. Create an empty node:
CREATE ()

  1. Create a generic relationship:
CREATE ()-[:RELATES_TO]->()

Proposed tags

[cypher] [graph-theory]

\$\endgroup\$
1
  • \$\begingroup\$ (1) This is a long way from being self-contained. What's Neo4j? (Sounds like a Java library). What's Cypher? (2) The operations need more explanation, particularly those which rely on properties which haven't been mentioned. (Reorder? But there's no position-in-order property. Operations on individual item: what's its identity?). (3) This site discourages questions which restrict answers to a single language unless there's a good reason for the restriction. I don't see a good reason here. \$\endgroup\$ Jul 6, 2019 at 7:54
1
\$\begingroup\$

Can the cursor reach the bottom?

A cursor position is valid if either of its two sides touches whitespace (i.e. a space or a newline(CR+LF or LF, depending on your OS)). The input will always consist of valid cursor positions.

This takes one input(a character matrix), and for a cursor on the up right corner of the input, can the cursor reach the bottom of the input?

Example input:

 ..... Same, delete text like this in order
 ......
. . . .
.      Same to get normal input
...... Same

The cursor can reach the bottom in this case. This process of moving the cursor will work: down, right(touches spaces on the left), down(touches spaces on the right), down, right(touches spaces on both sides) 6 times, and down(touching spaces and a linefeed).

Notably, this will also work:

  Code Golf deletes trailing whitespace by default
..
. trailing

The cursor starts at the up-right corner. After moving right two times, it can move down (due to touching a newline character). Then, it can move down, which touches the bottom of the line.

This example will not work:

 ...
... Same reason as above

The cursor cannot move down, as there is no sufficient whitespace to be touched.

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

Posted here

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Interesting challenge, but I'm afraid a lot of trivial solutions exist. E.g. 123 which prints 123 in many languages. More interesting would be to require all three/four characters to be unique, and that they be printed in reverse. \$\endgroup\$
    – Adám
    Jul 8, 2019 at 20:04
  • 2
    \$\begingroup\$ now that this has been posted, you can edit it to only include a link to your post and delete it :-) \$\endgroup\$
    – Giuseppe
    Jul 9, 2019 at 18:50
1
\$\begingroup\$

There's an echo in my array... echo in my array... my array...

Posted. Thanks for all of the suggestions and happy golfing!

\$\endgroup\$
11
  • \$\begingroup\$ "0≤n<1000" The input has 0–1000 elements or the elements are in the range 0–1000, or both? \$\endgroup\$
    – Adám
    Jul 8, 2019 at 21:24
  • \$\begingroup\$ Can there not be multiple correct solutions? \$\endgroup\$
    – Adám
    Jul 8, 2019 at 21:26
  • \$\begingroup\$ Will the echo ever begin at the first element? \$\endgroup\$
    – Adám
    Jul 8, 2019 at 21:26
  • \$\begingroup\$ I'm not sure I fully understand how the echo works. Why can [2,4,6] not be [1,2,3] with an echo overlapping at the first element? \$\endgroup\$
    – Adám
    Jul 8, 2019 at 21:31
  • \$\begingroup\$ In fact, would there be one solution for each step, so dividing the input by 2 is always a valid solution? \$\endgroup\$
    – Adám
    Jul 8, 2019 at 21:32
  • \$\begingroup\$ @Adám ah yes, that's why echo cannot begin at the first element. The echo'd version will always be longer than the original un-echoed version. I'll clarify that. \$\endgroup\$
    – 640KB
    Jul 8, 2019 at 21:33
  • \$\begingroup\$ @Adám have updated rules and test cases from your comments. Thanks! \$\endgroup\$
    – 640KB
    Jul 9, 2019 at 18:32
  • \$\begingroup\$ As suggestion: if there is no echo, don't output nothing or false - the challenge is to correct the echo. If there is none, the echo is corrected to be... no different from the input. In a bid for consistency, I would therefore suggest that if there is no echo, they should output the original input, since that is the 'normal' version of the array. \$\endgroup\$ Jul 10, 2019 at 8:09
  • \$\begingroup\$ Also, I'd suggest to make the program return the shortest possible array in the case of multiple solutions, to remove the most possible reverb - i.e choose the one that removes the most values from the input. \$\endgroup\$ Jul 10, 2019 at 13:42
  • \$\begingroup\$ @GezaKerecsenyi I've been trying to come up with a case where there are multiple solutions, and cannot. You can easily have many echo'd versions for a given un-echo'd version, but there seems to only be one or zero un-echo'd versions for an echo'd version. I'm not a mathematician, so I cannot conclusively prove this, and I'm happy to be proven wrong, but I don't see a way that a correctly-constructed echo'd version could produce more than one answer. \$\endgroup\$
    – 640KB
    Jul 10, 2019 at 14:52
  • 1
    \$\begingroup\$ @gwaugh after further consideration, I have come to the conclusion that you're correct. It's like a Fourier transform: every wave function always have a unique value, either in terms of phase or magnitude. Here, the phase is always different, and since the phase is shifted, the 'transform' of these numbers (imagining they are Y values at the X point of their index) must also be unique. So feel free to remove that rule - there can never be two answers. \$\endgroup\$ Jul 10, 2019 at 17:12
1
\$\begingroup\$

Story

I began studying the Collatz Conjecture

And noticed this pattern in the numbers that go to 1 in one odd step, like 5,10,20,21,40,42... and looke in up on OEIS and found this formula.

\$floor(sqrt(4*n + 1)) - 1\$

Which can plot these numbers in their natural order like so;

\$\frac{\left(8\cdot2^{\operatorname{floor}\left(\sqrt{4\operatorname{floor}\left(x\right)+1}\right)}-2^{\left(\operatorname{floor}\left(\sqrt{4\operatorname{floor}\left(x\right)+1}\right)-1-\operatorname{floor}\left(\frac{\left(4\operatorname{floor}\left(x\right)+1-\operatorname{floor}\left(\sqrt{4\operatorname{floor}\left(x\right)+1}\right)^2\right)}{2}\right)\right)}\right)}{3}\$

Then I looked at numbers going to 1 in two steps, like 3,6,12,13,24,26...
Where I found another pattern that I could not find a formula for on OEIS

long nth(int n){if(n>241)return -1;return (((1<<Y[n]+5)-(1<<1+Y[n]-((Z[n]&1)+Z[n]*3)))/3-(1<<Y[n]-2*X[n]-(2*(Z[n]&1)+Z[n]*3)))/3;}

With X[],Y[] and Z[] being these lookup-tables

 int[]X=new int[]{
 0, 
 0, 
 0,  1, 
 0,  1, 
 0,  1,  2, 
 0,  1,  2,                              0,
 0,  1,  2,  3,                          0,                          0, 
 0,  1,  2,  3,                          0,  1,                      0, 
 0,  1,  2,  3,  4,                      0,  1,                      0,  1, 
 0,  1,  2,  3,  4,                      0,  1,  2,                  0,  1, 
 0,  1,  2,  3,  4,  5,                  0,  1,  2,                  0,  1,  2,
 0,  1,  2,  3,  4,  5,                  0,  1,  2,  3,              0,  1,  2,                  0,
 0,  1,  2,  3,  4,  5,  6,              0,  1,  2,  3,              0,  1,  2,  3,              0,              0, 
 0,  1,  2,  3,  4,  5,  6,              0,  1,  2,  3,  4,          0,  1,  2,  3,              0,  1,          0, 
 0,  1,  2,  3,  4,  5,  6,  7,          0,  1,  2,  3,  4,          0,  1,  2,  3,  4,          0,  1,          0,  1, 
 0,  1,  2,  3,  4,  5,  6,  7,          0,  1,  2,  3,  4,  5,      0,  1,  2,  3,  4,          0,  1,  2,      0,  1, 
 0,  1,  2,  3,  4,  5,  6,  7,  8,      0,  1,  2,  3,  4,  5,      0,  1,  2,  3,  4,  5,      0,  1,  2,      0,  1,  2, 
 0,  1,  2,  3,  4,  5,  6,  7,  8,      0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  4,  5,      0,  1,  2,  3,  0,  1,  2,      0, 
 0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  0,  1,  2,  3,  1, 2
 };
 int[]Y=new int[]{
 0, 
 1, 
 2,  2, 
 3,  3, 
 4,  4,  4, 
 5,  5,  5,                              5,
 6,  6,  6,  6,                          6,                          6, 
 7,  7,  7,  7,                          7,  7,                      7, 
 8,  8,  8,  8,  8,                      8,  8,                      8,  8, 
 9,  9,  9,  9,  9,                      9,  9,  9,                  9,  9, 
10, 10, 10, 10, 10, 10,                 10, 10, 10,                 10, 10, 10,
11, 11, 11, 11, 11, 11,                 11, 11, 11, 11,             11, 11, 11,                 11,
12, 12, 12, 12, 12, 12, 12,             12, 12, 12, 12,             12, 12, 12, 12,             12,             12, 
13, 13, 13, 13, 13, 13, 13,             13, 13, 13, 13, 13,         13, 13, 13, 13,             13, 13,         13, 
14, 14, 14, 14, 14, 14, 14, 14,         14, 14, 14, 14, 14,         14, 14, 14, 14, 14,         14, 14,         14, 14, 
15, 15, 15, 15, 15, 15, 15, 15,         15, 15, 15, 15, 15, 15,     15, 15, 15, 15, 15,         15, 15, 15,     15, 15, 
16, 16, 16, 16, 16, 16, 16, 16, 16,     16, 16, 16, 16, 16, 16,     16, 16, 16, 16, 16, 16,     16, 16, 16,     16, 16, 16, 
17, 17, 17, 17, 17, 17, 17, 17, 17,     17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,     17, 17, 17, 17, 17, 17, 17,     17, 
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18
};
int[]Z=new int[]{
0, 
0, 
0,  0, 
0,  0, 
0,  0,  0, 
0,  0,  0,                              1,
0,  0,  0,  0,                          1,                          2, 
0,  0,  0,  0,                          1,  1,                      2, 
0,  0,  0,  0,  0,                      1,  1,                      2,  2, 
0,  0,  0,  0,  0,                      1,  1,  1,                  2,  2, 
0,  0,  0,  0,  0,  0,                  1,  1,  1,                  2,  2,  2,
0,  0,  0,  0,  0,  0,                  1,  1,  1,  1,              2,  2,  2,                  3,
0,  0,  0,  0,  0,  0,  0,              1,  1,  1,  1,              2,  2,  2,  2,              3,              4, 
0,  0,  0,  0,  0,  0,  0,              1,  1,  1,  1,  1,          2,  2,  2,  2,              3,  3,          4, 
0,  0,  0,  0,  0,  0,  0,  0,          1,  1,  1,  1,  1,          2,  2,  2,  2,  2,          3,  3,          4,  4, 
0,  0,  0,  0,  0,  0,  0,  0,          1,  1,  1,  1,  1,  1,      2,  2,  2,  2,  2,          3,  3,  3,      4,  4, 
0,  0,  0,  0,  0,  0,  0,  0,  0,      1,  1,  1,  1,  1,  1,      2,  2,  2,  2,  2,  2,      3,  3,  3,      4,  4,  4, 
0,  0,  0,  0,  0,  0,  0,  0,  0,      1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,      3,  3,  3,  3,  4,  4,  4,      5, 
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  5, 5
};

Challenge

The challenge is to write a "reasonably fast" function or expression that replaces and extends these lookup tables.
Think of the lookup tables as a 3D structure. Pictured is the top 720 boxes of this structure.

challenge

Input

An integer which is the index of a cube in the structure. You can assume the input will be in the range 0 to 719 inclusive.

Output

The x,y,z coordinates for the given index. Assuming the input is between 0 and 719 the output ranges are x, 0 to 13 y, 0 to 27 z, 0 to 8

It's fine to accept and return larger indexes correctly just not required.

Examples

    i  ->   x   y   z
    0  ->   0,  0,  0
   12  ->   0,  5,  1
   30  ->   4,  8,  0
   65  ->   2, 11,  1
  100  ->   0, 13,  2
  270  ->   1, 19,  3
  321  ->   1, 20,  6
  719  ->   1, 27,  8

If you collapse the z-coordinate, then the structure is indexed top-down left right like shown below; Examples are marked in square brackets []

Y,Z 0,
 0   | [0]  
 1   |  1 
 2   |  2   3 
 3   |  4   5 
 4   |  6   7   8                                1,
 5   |  9  10  11                                 |[12]                           2,
 6   | 13  14  15  16                             | 17                             | 18 
 7   | 19  20  21  22                             | 23  24                         | 25 
 8   | 26  27  28  29 [30]                        | 31  32                         | 33  34 
 9   | 35  36  37  38  39                         | 40  41  42                     | 43  44 
10   | 45  46  47  48  49  50                     | 51  52  53                     | 54  55  56                    3,
11   | 57  58  59  60  61  62                     | 63  64 [65] 66                 | 67  68  69                     | 70                4,
12   | 71  72  73  74  75  76  77                 | 78  79  80  81                 | 82  83  84  85                 | 86                 | 87 
13   | 88  89  90  91  92  93  94                 | 95  96  97  98  99             [100] 101 102 103                |104 105             |106 
14   |107 108 109 110 111 112 113 114             |115 116 117 118 119             |120 121 122 123 124             |125 126             |127 128 
15   |129 130 131 132 133 134 135 136             |137 138 139 140 141 142         |143 144 145 146 147             |148 149 150         |151 152 
16   |153 154 155 156 157 158 159 160 161         |162 163 164 165 166 167         |168 169 170 171 172 173         |174 175 176         |177 178 179        5,
17   |180 181 182 183 184 185 186 187 188         |189 190 191 192 193 194 195     |196 197 198 199 200 201         |202 203 204 205     |206 207 208         |209    6, 
18   |210 211 212 213 214 215 216 217 218 219     |220 221 222 223 224 225 226     |227 228 229 230 231 232 233     |234 235 236 237     |238 239 240 241     |242     |243 
19   |244 245 246 247 248 249 250 251 252 253     |254 255 256 257 258 259 260 261 |262 263 264 265 266 267 268     |269[270]271 272 273 |274 275 276 277     |278 279 |280
20   |281 282 283 284 285 286 287 288 289 290 291 |292 293 294 295 296 297 298 299 |300 301 302 303 304 305 306 307 |308 309 310 311 312 |313 314 315 316 317 |318 319 |320[321]
  X->|  0   1   2   3   4   5   6   7   8   9  10 |  0   1   2   3   4   5   6   7 |  0   1   2   3   4   5   6   7 |  0   1   2   3   4 |  0   1   2   3   4 |  0   1 |  0   1  

Note that at even y-coordinates the structure expands in the x-direction, and at 0 and 5 mod 6 in the z-direction. Expect for the very top block.

Rules

This is code-golf, the shortest code in bytes wins.

Reasonably fast As an additional requirement although not a competition of fastest code,
the code must still be shown to compute coordinates in a reasonable amount of time. You may for example use try it online and run a loop through all coordinates under 720 without exceeding the time limit of a minute, printing is optional.

If you fail this rule, mark your answer with non competing

"storing information as you go" is forbidden. For example executing f(100) should not depend on having computed f(99) previously.

Lookup tables are allowed but included in bytecount so aim to make them sparse if you choose to use them.

Example code

non-competing

coord coords(int index){
int a=0,b=0,c=0;
int x=0,y=0,z=0;
long n,k,one;  
n = k = 3;
int t=0;
while(t<index){
int s=0;k++;n=k;
while(n>1 && s<4){ n/=n&-n;n=n*3+1; n/=n&-n;s++;}
if(s==2)t++;
}
n=k; 
one=n&-n;k = one;while(k>1){k>>=1;c++;} n=3*n+one;
one=n&-n;k = one;while(k>1){k>>=1;b++;} n=3*n+one;
one=n&-n;k = one;while(k>1){k>>=1;a++;} 
coord r;
r.x = (b-c-1)>>1;
r.y = a-5;
r.z = (a-b-2)/6 +(a-b-4)/6;
return r;
}

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Will the input always be between 0 and 321 (inclusive)? \$\endgroup\$
    – mkst
    Jul 10, 2019 at 6:27
  • \$\begingroup\$ Good question, let's go with 797 @streetster \$\endgroup\$ Jul 10, 2019 at 10:59
  • \$\begingroup\$ @streetster 719.. i counted the boxes wrong, good thing I began in the sandbox \$\endgroup\$ Jul 11, 2019 at 17:58
1
\$\begingroup\$

Decode a RISC-V J-type immediate

RISC-V is an open processor instruction set, which defines a somewhat typical RISC instruction set. However, in order to make decoding simpler in hardware, the encoding for immediate values tends to be quite complex, with the bits essentially shuffled around. And the worst offender for that is without a doubt the type J (jump) instruction type.

So, the challenge is, given a (non-compressed) RISC-V instruction word, decode and output its type J immediate part.

A type J instruction has the following format:

   31      30-21     20       19-12   11-7  6-0
|imm[20]|imm[10:1]|imm[11]|imm[19:12]| rd |opcode|

The only fields we are interested in are the imm fields. The immediate is sign extended, and its least significant bit is always 0, so the immediate (in term of instruction bits) is:

    31-20       19-12       11        10-1     0
|...inst[31]|inst[19:12]|inst[20]|inst[30:21]| 0 |

Sample pseudocode: 0xFFF00000 * ((instr >> 31) & 1) | (instr & 0x000FF000) | ((instr & 0x100000) >> 9) | ((instr & 0x7FE00000) >> 20).

Test cases

I: 0x4DFAB06F (j 0xABCDE)
O: 0x000ABCDE

I: 0xFD9FF0EF (jal ra, -0x28)
O: 0xFFFFFFD8

I: 0x8000006F (j -0x100000)
O: 0xFFF00000

The answer with the smallest byte count wins, standard loopholes apply, etc... Your program may take input and write output in any format it requires.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It took a bit of puzzling to figure out the second code block. The ... notation is liable to misunderstanding (I'm not sure whether JS developers would find it more or less confusing), and there's no clear reason for 10-5 and 4-1 to be split up. This is one case where a reference implementation in generic C-like pseudocode could help: I think 0xfff00000 * ((imm >> 31 & 1)) | (imm & 0x000ff000) | ((imm & 0x00100000) >> 9) | ((imm & 0x7fe00000) >> 20) is correct and fairly generic. (In particular, I've deliberately avoided making assumptions about how the sign bit is treated under >>). \$\endgroup\$ Jul 16, 2019 at 8:10
  • 1
    \$\begingroup\$ @PeterTaylor I copied the instruction format diagram from the RISC-V specification and I didn't realize the 10-5 and 4-1 parts could be merged. Oops. And I added a pseudocode for the decoding. \$\endgroup\$ Jul 16, 2019 at 11:38
1
\$\begingroup\$

Alphanumeric Line and Curve Counting

Posted here.

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

Bits and Bytes constant generation

In this challenge, you have to generate the shortest Bits and Bytes program that outputs an integer input. For the simplicity of the challenge, you only have to search with ! and <.

Bits and Bytes quick reference

Bits and Bytes operates on a one-byte accumulator. There are 4 operations (only 2 are neccecary for this challenge):

  • ! : Invert all of the bits in the accumulator
  • < : Shifts all bits in the accumulator one bit to the right. The leftmost bit becomes a 0 and the rightmost bit is discarded.
  • > : Shift right
  • @ : Swap nybbles

Input / Output

Input will be two integers. The first integer sets the accumulator to the value of that integer. The second integer indicates the resulting value. Your program should output the shortest program in Bits and Bytes that sets the accumulator to that value.

Examples

0
255
!
0
4
!<!<!<

This is a contest; the shortest program wins.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'd recommend having the question be self contained and explaining what the instructions actually do \$\endgroup\$
    – Jo King Mod
    Jul 21, 2019 at 11:34
  • 2
    \$\begingroup\$ This is similar enough to some previous challenges that I wouldn't be surprised if someone finds a dupe. Also, should there be a second input for the starting value of the accumulator? \$\endgroup\$ Jul 21, 2019 at 23:04
1
\$\begingroup\$

WANTEDM?VEMENTANDACALMCOURSE?FE???UENCE

Challenge

Inspired by puzzles appearing on my website's chat, your job (should you choose to accept it) is to accept a string (say (?@Nbgkx¨¾ÃÐÕã÷øĆĊċĎďěĨīĺŏšŴŹǣǩǮ˘͵ΖΫΰξρφ) and:

  • Find the Unicode points for the string: [40, 63, 64, 78, 98, 103, 107, 120, 168, 190, 195, 208, 213, 227, 247, 248, 262, 266, 267, 270, 271, 283, 296, 299, 314, 335, 353, 372, 377, 483, 489, 494, 728, 885, 918, 939, 944, 958, 961, 966]
  • Find the differences between elements: [23, 1, 14, 20, 5, 4, 13, 48, 22, 5, 13, 5, 14, 20, 1, 14, 4, 1, 3, 1, 12, 13, 3, 15, 21, 18, 19, 5, 106, 6, 5, 234, 157, 33, 21, 5, 14, 3, 5]
  • For every element in the differences between elements:
    • If the element is less than 27, add it by 64 and output it converted to a Unicode character (e.g. 1 -> "A", 2 -> "B", \$\ldots\$ ).
    • If the element is greater than or equal to 27, output a non-alphabet character ([^A-Za-z])

Test Cases

The test cases output in uppercase and use the question mark for the non-alphabet character.

(?@Nbgkx¨¾ÃÐÕã÷øĆĊċĎďěĨīĺŏšŴŹǣǩǮ˘͵ΖΫΰξρφ --> WANTEDM?VEMENTANDACALMCOURSE?FE???UENCE
!1CRYkly¤´ÉãýĉĎġĢİĴķņŊŏŖťűŷ --> PROGRAM?PUZZLESANDCODEGOLF
!$37<CR^deswz¤«®¶·ÃÏÔâéîā --> CODEGOLFANDC?GCHALLENGES
!5=BShqt¢¹ÇÍÜôþēĠİĵĹňŞţŵƉƑƖƢƣƽǖǚǩǰȃ -> THEQUIC?WNFOXJUMPEDOVERTHELAZYDOGS

Notes

  • The difference between the Unicode points for the string will always be greater than 0.
  • The input's Unicode points will be strictly increasing.
  • You may output in lowercase.
  • The non-alphabet character does not need to be consistent.
\$\endgroup\$
4
  • \$\begingroup\$ I suggest using less than or equal to 26, so that Z can be represented \$\endgroup\$
    – wastl
    Aug 1, 2019 at 12:59
  • \$\begingroup\$ @wastl Yeah, done \$\endgroup\$
    – MilkyWay90
    Aug 1, 2019 at 16:07
  • 1
    \$\begingroup\$ What stops us from just adding 97 to all the differences, since outside that range is non-alphabetical? \$\endgroup\$
    – Jo King Mod
    Aug 2, 2019 at 4:09
  • 1
    \$\begingroup\$ @JoKing Nothing stops you from doing that. \$\endgroup\$
    – MilkyWay90
    Aug 2, 2019 at 4:54
1
63 64
65
66 67
145

You must log in to answer this question.

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