555
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

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

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3928 Answers 3928

1
5 6
7
8 9
131
5
\$\begingroup\$

Ouput Input... Forever

Problem

Given input chars, output them repeatedly forever.

Examples

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

Dedication: This is for all the tarpits out there!

Questions

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

Create the shortest code snippet of the power functions 1 through 10 which can be compiled to assembly code and which contains the minimum number of imul assembly operations. For better comparison use https://godbolt.org/ and either GCC or LLVM.

Introduction

Did you know the fastest way to calculate x⁴ is not x*x*x*x, but y = x*x; y*y which saves one multiplication and is therefore faster. In mathematics and computer science this is called addition-chain exponentiation.

The minimum number of multiplications for powers of 1 through 10 are

x^1  -> 0
x^2  -> 1
x^3  -> 2
x^4  -> 2
x^5  -> 3
x^6  -> 3
x^7  -> 4
x^8  -> 3
x^9  -> 4
x^10 -> 4

Example

The assembly code looks as follows (C++ code below):

pow_1(int):
        mov     eax, edi
        ret
pow_2(int):
        mov     eax, edi
        imul    eax, edi
        ret
pow_3(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, edi
        ret
pow_4(int):
        imul    edi, edi
        mov     eax, edi
        imul    eax, edi
        ret
pow_5(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, edi
        ret
pow_6(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, edi
        imul    eax, eax
        ret
pow_7(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, edi
        ret
pow_8(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, eax
        ret
pow_9(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, eax
        imul    eax, edi
        ret
pow_10(int):
        mov     eax, edi
        imul    eax, edi
        imul    eax, eax
        imul    eax, edi
        imul    eax, eax
        ret

One naive solution written in C/C++ and compiled with X86-64 gcc 11.2 and -O3 optimization on https://godbolt.org/ could be (Notice that I didn't need to optimize the code myself, but the compiler picked it up automatically. Aren't compilers awesome?):


int pow_1(int num) {
    return num;
}

int pow_2(int num) {
    return num * num;
}

int pow_3(int num) {
    return num * num * num;
}

int pow_4(int num) {
    return num * num * num * num;
}

int pow_5(int num) {
    return num * num * num * num * num;
}

int pow_6(int num) {
    return num * num * num * num * num * num;
}

int pow_7(int num) {
    return num * num * num * num * num * num * num;
}

int pow_8(int num) {
    return num * num * num * num * num * num * num * num;
}

int pow_9(int num) {
    return num * num * num * num * num * num * num * num * num;
}

int pow_10(int num) {
    return num * num * num * num * num * num * num * num * num * num;
}

Of course you can also use other language like Rust to create the same assembly code:

pub fn pow_9(num: i32) -> i32 {
    num * num * num * num * num * num * num * num * num
}

(Note Rust has an additional mov, but the challenge only focuses on the amount of imul assembly instructions.)

example::pow_9:
        mov     eax, edi
        mov     ecx, edi
        imul    ecx, edi
        imul    ecx, ecx
        imul    eax, ecx
        imul    eax, ecx
        ret

Scoring

  • The string must be compilable to assembly instruction with a compiler like GCC or LLVM (Note they have backends for many languages). You are not allowed to create the assembly instructions directly. Please also provide compiler version and flags.
  • The whole string must be written in the same language (no writing C with another language)
  • Out of bounds issues must not be considered, the code should work for integers 0 through 3.
  • The generated assembly code can only contain the minimum number of imul needed for that power and mov and ret instructions
  • The 10 functions in the assembly instructions should be named as I named them (order does not matter)
  • Shortest string wins!

Good luck!

Discussion

I've mistakenly posted this as a question to the meta site, but wanted this was my intended destination. After a few migrations the current location is here. I've now reposted here trying to keep the style the same as I couldn't edit the post anymore.

Grain ghost has made two comments on how to improve the challenge:

  • "Creating the assembly instructions not via a compiler is not allowed" and "The generated assembly must be similar to the provided assembly" strike me as not particularly clear, objective or enforceable
  • Since we are dealing with assembly I would expect some discussion about precision and out of bounds issues

Thank you!

This is not a typical code golf challenge, but I'm very excited what kinds of meta programming techniques will show up.

\$\endgroup\$
10
  • \$\begingroup\$ @grain-ghost do I ping you this way? What I want to prohibit with the use of a compiler is that people simple create a program creating the assembly instruction string. The string must be compilable with GCC or LLVM. Similarity is hard, because compilers are weird (see my Rust example). May be say: The binary must contain the right number of imul instructions, at most two additional mov instruction and one ret instruction. Precision is no important with integer numbers as far I can think. Overflow is an issue, but I would simply neglect that case or restrict to numbers below or equal to 3. \$\endgroup\$
    – JulianWgs
    Nov 16, 2021 at 20:54
  • 1
    \$\begingroup\$ If nobody's said it so far, welcome to Code Golf! This looks like a great challenge. For out of bounds issues, there's usually one of two approaches challenges will take, either having a minimum input size that must be supported, or just ignoring out of bounds issues within reason. Those would probably both work here, so it's entirely up to you. I agree with the two bullet points Grain Ghost brought up, those could probably use some clarification. \$\endgroup\$ Nov 16, 2021 at 21:06
  • \$\begingroup\$ Thanks for welcoming me! :) I've updated the challenge. By restricting the amount of assembly instructions the submission must use imul (another feedback brought up to use for loops with addition) and guarantees similarity, because there is no other way to solve it. Another idea I had would be to only allow mov, ret and imul instructions. \$\endgroup\$
    – JulianWgs
    Nov 16, 2021 at 21:24
  • 1
    \$\begingroup\$ Oh, so you're aiming to restrict what instructions can be used? That makes sense, I hadn't understood the wording right. You can definitely just choose a specific list of instructions to allow, which I'd recommend doing instead of the current requirements which are a little bit vague. There's actually a tag for that sort of thing, atomic-code-golf. \$\endgroup\$ Nov 16, 2021 at 21:27
  • 1
    \$\begingroup\$ (Comment migrated from the original question.) In addition to what was already pointed out on the main site, another potential issue with this challenge is that it's entirely possible to do it without any imul, for instance with inefficient addition loops. \$\endgroup\$
    – Arnauld
    Nov 16, 2021 at 21:32
  • \$\begingroup\$ I've updated the challenge accordingly I think limiting to imul (minimum number), mov and ret ensures similarity. I would like to encourage entries from many languages. Can I pick a winner per language? \$\endgroup\$
    – JulianWgs
    Nov 16, 2021 at 22:04
  • \$\begingroup\$ We have a challenge on a similar topic Shortest Addtion Chain. This challenge looks different enough though. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 2:00
  • 2
    \$\begingroup\$ I might not be the target audience as someone not into compiled languages, but the needing to go through a compiler strikes me as convoluted. What if we could just output the assembly, or some other representation of the sequence of operations? Needing to consider how a compiler would translate and optimize the operations seems finicky, but I guess maybe that's the whole point. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 2:06
  • \$\begingroup\$ @xnor exactly the best solution will probably involve some kind of metaprogramming massaging the code so the compiler will optimize it. I've updated the challenge again with info about naming the functions. Can the challenge be posted now? :) \$\endgroup\$
    – JulianWgs
    Nov 17, 2021 at 7:00
  • 1
    \$\begingroup\$ @JulianWgs It's your decision, but the general recommendation is to leave posts in the Sandbox at least 72 hours to gather feedback. I'd err on the side of waiting for this challenge because it might benefit from being seen by more people with knowledge in this specific domain and many people don't look at the Sandbox that often. I'd also suggest confirming with existing commenters that your edits have addressed their comments. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 7:06
5
\$\begingroup\$

Open or close?

Posted here.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The calculator would be more useful if ) were followed by ) assuming another unbalanced ( remains. Example: "1*(2+(3*4)" -> ? \$\endgroup\$
    – aschepler
    Nov 15, 2021 at 23:24
  • \$\begingroup\$ @aschepler Good thing the calculator dev thought this through more than I did, because that's exactly what it does. I'll update the question, thanks! \$\endgroup\$
    – Jitse
    Nov 16, 2021 at 8:11
5
\$\begingroup\$

Convert prefix to infix

\$\endgroup\$
2
  • \$\begingroup\$ Dupe? \$\endgroup\$
    – Dingus
    Nov 18, 2021 at 23:09
  • \$\begingroup\$ @Dingus Yes, I'll just do prefix to infix instead :P \$\endgroup\$
    – emanresu A
    Nov 19, 2021 at 3:31
5
\$\begingroup\$

Minimum number of changed tiles to permit knight passage

Summary

Given a chess knight K that is only allowed to step on permitted tiles X, output the minimum number of . tiles that must be changed to an X tile in order to permit a passage to the destination D.

Specification

  • The chessboard is guaranteed to be larger than 3x3.
  • The chessboard is guaranteed to have one and only one D and K in it.
  • Sometimes, not using the existing X tiles can lead to a more minimal solution, so please take this in mind while solving this challenge. (e.g. the 2nd testcase)

Test cases

..D.
XXXX
....
...K

Output = 1 (sequence = (-2,+1), (+1,+2))

.D..
....
..XK
....

Output = 2: (sequence = (-2,+1), (-1,-2), (+2, +1), (-1, +2))

D.X
...
...
...
..K

Output = 1: (sequence: (-1, +2), (-1, +2))

DX.
...
...
...
..K

Output = 1: (sequence: (-1, +2), (-1, +2))

D.X.
....
.X.X
.K..

Output = 0: (sequence: (+2, +1), (-1, +2), (-1, -2), (-1, +2))

DXXX
XKXX
XXXX
XXXX

Output = 0: (sequence: (+1, -2), (+1, +2), (-2, +1), (-1, -2), (+2, +1), (-2, +1))

\$\endgroup\$
14
  • \$\begingroup\$ where is the D on the board and what is the W doing on the board \$\endgroup\$
    – DialFrost
    Jan 26 at 7:08
  • 1
    \$\begingroup\$ @DialFrost That's a typo. Fixed \$\endgroup\$
    – user110579
    Jan 26 at 7:10
  • \$\begingroup\$ i like this challenge otherwise! \$\endgroup\$
    – DialFrost
    Jan 26 at 7:15
  • \$\begingroup\$ @DialFrost Thank you! :) \$\endgroup\$
    – user110579
    Jan 26 at 7:22
  • \$\begingroup\$ May we assume that using existing X tiles leads to minimal solution or may there be "traps"? \$\endgroup\$
    – pajonk
    Jan 26 at 8:08
  • \$\begingroup\$ May you give an example of not using the X tiles leading to the minimal solution? \$\endgroup\$
    – user110579
    Jan 26 at 8:12
  • \$\begingroup\$ I mean e.g. DX./.../.../.../..K, where putting X in the middle is sufficient and you don't need to reach the existing X. \$\endgroup\$
    – pajonk
    Jan 26 at 8:12
  • 1
    \$\begingroup\$ @pajonk In this case, I think I'm trying to define a challenge that allows "traps" in the input. I'll clarify that in the challenge. \$\endgroup\$
    – user110579
    Jan 26 at 8:14
  • \$\begingroup\$ I've edited my example in the meantime to highlight its "trappy" nature. You may also want to add more test-cases (like with more Xs or where the ouput is 0). \$\endgroup\$
    – pajonk
    Jan 26 at 8:18
  • \$\begingroup\$ @pajonk I've added your edited testcase and some of your testcase suggestions. Thank you for your suggestions! \$\endgroup\$
    – user110579
    Jan 26 at 8:27
  • \$\begingroup\$ your first test case is wrong, you can do it in 1: (-2,+1), (+1,+2) \$\endgroup\$ Jan 26 at 14:06
  • \$\begingroup\$ @thejonymyster Fixed \$\endgroup\$
    – user110579
    Jan 27 at 4:57
  • \$\begingroup\$ suggested testcase: one where the straight path to the goal takes more X tile placements than following a longer route to the goal which already has many X tiles. Either way though, this is pretty much ready to post \$\endgroup\$ Jan 28 at 14:13
  • \$\begingroup\$ May I assume the board is less than (or equals to) 8x8? \$\endgroup\$
    – tsh
    Jan 29 at 8:15
5
\$\begingroup\$
\$\endgroup\$
3
  • \$\begingroup\$ It'd be nice to link the ITTM paper. Also, showing an example ITTM and explaining its halting time (like your ⍵×⍵ 2-state ITTM) would be helpful. \$\endgroup\$
    – user41805
    May 7, 2021 at 12:39
  • \$\begingroup\$ @user41805 I'm currently working on an explanation for my 2-state ITTM champion. But the animations are a bit time consuming. I meant to link some ITTM papers, so I will add those links when I finish the edit I am working on. Thanks. \$\endgroup\$
    – Wheat Wizard Mod
    May 7, 2021 at 12:42
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/36747/45613 and codegolf.stackexchange.com/questions/18028/… (This doesn't seem to be a duplicate) \$\endgroup\$
    – Beefster
    May 18, 2021 at 16:25
5
\$\begingroup\$

Is it a fibonacci-like sequence?

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

Fibonacci triangle

\$\endgroup\$
8
  • \$\begingroup\$ this is more of a curve due to the incrementing length of numbers :P looks alright tho \$\endgroup\$
    – DialFrost
    Mar 2 at 3:47
  • \$\begingroup\$ @DialFrost Close enough, and I wasn't sure what else to call it :P \$\endgroup\$
    – emanresu A
    Mar 2 at 3:48
  • \$\begingroup\$ i think the test case for 20 is wrong, the first 1+1=2 and 1+2=3 dont align \$\endgroup\$
    – DialFrost
    Mar 2 at 3:48
  • \$\begingroup\$ @DialFrost Fixed, that's an error with my programming \$\endgroup\$
    – emanresu A
    Mar 2 at 3:51
  • \$\begingroup\$ suggestion for title qns: Fibonacci curve (cuz triangle has no application to this qns lol) \$\endgroup\$
    – DialFrost
    Mar 2 at 4:17
  • \$\begingroup\$ Is infinite output allowed, taking no input? (part of standard sequence rules) \$\endgroup\$
    – pxeger
    Mar 2 at 10:17
  • \$\begingroup\$ @pxeger Sure :P - no outputting the nth term though, as I feel that makes the challenge too easy. \$\endgroup\$
    – emanresu A
    Mar 2 at 19:03
  • 1
    \$\begingroup\$ @emanresuA Yes, I was thinking that as well. (although calculating the increasing string lengths might be complicated?) \$\endgroup\$
    – pxeger
    Mar 2 at 20:09
5
\$\begingroup\$

Gray code on N symbols

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

Resolve references in a chat discussion

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

Pairs of integers ordered by their exponentiation

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

Convert between graph representations.

\$\endgroup\$
2
  • \$\begingroup\$ Awesome challenge! It seems ready to me and juding by the upvotes (might wanna wait 1 or 2 more days) \$\endgroup\$
    – DialFrost
    Mar 21 at 11:00
  • \$\begingroup\$ @DialFrost already posted .... \$\endgroup\$
    – PyGamer0
    Mar 21 at 12:21
5
\$\begingroup\$

Satisfy as many people as possible

Posted here.

\$\endgroup\$
2
  • \$\begingroup\$ im confused but nice challenge! :D \$\endgroup\$
    – DialFrost
    Mar 14 at 2:50
  • \$\begingroup\$ Wow, good challenge! They should use this for making servant robots; they'd make everyone as happy as possible :-)! The only part I didn't understand was the math formula; but, since I don't even know what the giant E means, that's not surprising. And as for title suggestions, something a little more catchy would be nice. Maybe something along the lines of "How many people can you satisfy?" (that's just a suggestion; I'm not very good at creative writing) \$\endgroup\$ Mar 22 at 19:37
5
\$\begingroup\$

Unshuffle my poker chips

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

Storing a band matrix

\$\endgroup\$
2
  • \$\begingroup\$ Can you clarify in the definition that a band is symmetric (in terms of shape) about the main diagonal? Something like "the main diagonal and an equal number of adjacent diagonals on either side of it" \$\endgroup\$
    – att
    May 9 at 23:02
  • \$\begingroup\$ Wait never mind, somehow I missed the "in this challenge" further down \$\endgroup\$
    – att
    May 9 at 23:04
5
\$\begingroup\$

BitCycle Metagolf

\$\endgroup\$
2
  • \$\begingroup\$ Since undefined behavior can have an effect on how small you can make a BitCycle program, I'd say you should either pick a specific implementation and say all answers must work on that implementation, or say that answers are allowed to work on any existing implementation. \$\endgroup\$
    – DLosc
    May 14 at 17:47
  • \$\begingroup\$ @DLosc Okay, I will put in that it has to work on TIO. \$\endgroup\$
    – Aiden Chow
    May 14 at 18:13
5
\$\begingroup\$

Spend maximal money

\$\endgroup\$
20
  • \$\begingroup\$ For 10.00; [5,5,10] is [5,5] an ok output? What should be the output for 10.00; [1,2,5,5,7] (and why)? Suggestion: keep the challenge within positive integers. \$\endgroup\$
    – pajonk
    May 9 at 11:15
  • \$\begingroup\$ @pajonk I prioritized choosing items from left to right. \$\endgroup\$ May 9 at 22:22
  • \$\begingroup\$ You may want to alter the new examples to comply with your spec ("without equaling"). Also, does the order of the output matter ([12.99, 0.99] vs [0.99, 12.99])? I also suggest explicitly stating that \$l\$ is an ordered list. \$\endgroup\$
    – pajonk
    May 10 at 9:06
  • \$\begingroup\$ @pajonk YOU were the one how made me thought those were the correct answers, but ok. \$\endgroup\$ May 10 at 11:26
  • \$\begingroup\$ and no, it will not be an ordered list. the output also doesn't matter. \$\endgroup\$ May 10 at 19:03
  • \$\begingroup\$ If the input is not ordered, hot do we determine left-to-right? \$\endgroup\$
    – pajonk
    May 10 at 19:31
  • \$\begingroup\$ aw damn you have a valid point lemme fix that \$\endgroup\$ May 10 at 22:16
  • \$\begingroup\$ Your last example has an incorrect output. The answer should be [2.00, 7.00] \$\endgroup\$
    – jezza_99
    May 12 at 23:31
  • \$\begingroup\$ @jezza_99 fixed. \$\endgroup\$ May 13 at 0:03
  • \$\begingroup\$ You say that you want to prioritize choosing items from left to right. For the examples you have given, this only results in an ordered output, which you've said is not important. The actual possible solutions do not change. I recommend either adding an example to test this criteria or dropping it. A suitable example would be budget=10.00, prices=[1.00, 2.00, 3.00, 4.00, 8.00]. This should output [1.00, 8.00] even though [2.00, 3.00, 4.00] is also a potential solution \$\endgroup\$
    – jezza_99
    May 13 at 1:03
  • \$\begingroup\$ @jezza_99 i'm sorry but you've broken my brain. I'll just leave this here to rot \$\endgroup\$ May 13 at 19:06
  • \$\begingroup\$ @BowlingPizzaBall what is the point of the rule "Prioritize choosing items from left to right"? \$\endgroup\$
    – jezza_99
    May 13 at 22:59
  • \$\begingroup\$ @jezza_99 Guess you could say there is no point. I'll remove that rule \$\endgroup\$ May 13 at 23:11
  • \$\begingroup\$ @jezza_99 I thought this rule was to make the solution unique. Now (as in your example above) there may be multiple solutions. \$\endgroup\$
    – pajonk
    May 14 at 15:31
  • \$\begingroup\$ @jezza_99, yeah, prioritizing left to right means there is only 1 valid solution. \$\endgroup\$ May 14 at 16:47
4
\$\begingroup\$

I attempted a problem I threw out as a suggested for 1p5.

In c, lex and yacc I needed more than 9600 characters ungolfed (fully commented, errors handled, some debugging code left in place, but some efficiency sacrificed in the name of shorter code), which seems pretty long, but c is about the most pessimal language you could choose for this problem except fortran 77 or something from the Turing Tarpit. The reference implementation can run its own build, which has some of that bootstrapping voodoo.

None-the-less, this is a relatively big project, and I don't want to post it unless people feel it is both well specified and interesting.

As yet there is no validation script, and I am not sure how one could be written as the acceptable output order could be post-order depth first or post-order breadth first and there is a left-first vs. right-first ambiguity on both. What a bother.

Aside: I'm quite proud of the lex and yacc part of my code, as I consider it spiffy.


A minimal implementation of the make (1) utility.

By minimal I mean,

  • No built in rules, and no pattern or suffix rules.
  • No variables and therefore no variable assignment or manipulations; also no variable expansion which includes no expansion of environment variables.
  • No automatic variables like $< and $@.

This only leaves constructs (called rules) of the form

<target> ":" <prerequisite>* "\n" ["\t" <action> "\n"]*

Where each <target> and <prerequisite> is a whitespace delimited string which may (or may not) represent a filename. Empty lines have no effect and "#" marks the beginning of a end of line comment (the sequence "#[^\n]*\n" should be treated as "\n" so it does not interfere with rules; this has the side effect of making "#" illegal in targets, prerequisites and actions). Colons are prohibited in identifiers.

The program should take its input from the standard input or by reading a file called "makefile" - implementer's choice. The program then attempts to "build" every target named on the command line. Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error and cause the program to exit before execution of any rules. In the event that no target is named on the command line, default to building the first target in the input.

Duplicate targets may (not must!) be treated as an error.

A target is deemed already built if

  1. It names an existing file and
  2. All its prerequisites are fulfilled

Otherwise it is built by

  1. Building all unfulfilled prerequisites then
  2. Running each <action> sequentially in the order they appear in the input, and if the action returns an exceptional exit state, stopping the program.

A prerequisite is deemed fulfilled if

  • The prerequisite represents an existing file and
  • The prerequisite is built and
  • The target is "newer" than the (fully built) prerequisite

A target is deemed "older" (i.e. not "newer") than its prerequisite if one of

  • Both represent files and the prerequisite has been modified more recently than the target.
  • The target does not represent an existing file, and the prerequisite does.

apply.

Authors on systems which do not support fork/exec semantics may write a batch file or script which is invoked as the program terminates, but that script must stop on the first unsuccessful action.

Sample Input

# Babymake compatible makefile for babymake
all:babymake

babymake : lex.yy.o  y.tab.o  babymake.o 
    cc -o babymake lex.yy.o y.tab.o babymake.o

babymake.o : babymake.c babymake.h
    cc -c babymake.c

lex.yy.o: lex.yy.c y.tab.h
    cc -c lex.yy.c

lex.yy.c : babymake.l
    lex babymake.l

y.tab.o: y.tab.c babymake.h
    cc -c y.tab.c

y.tab.c : babymake.y  
    yacc -d babymake.y

clean:
    rm -f babymake.o  lex.yy.o  y.tab.o

cleaner: clean # just testing end of line comments
    rm -f y.tab.c y.tab.h
    rm -f lex.yy.c

bogus: boguser 
    echo "building bogus" # test in another context

Sample output

$ ./babymake < babymake.example cleaner
 rm -f babymake.o  lex.yy.o  y.tab.o
 rm -f y.tab.c y.tab.h
 rm -f lex.yy.c
$ ./babymake < babymake.example all    
 cc -c babymake.c
 yacc -d babymake.y
 cc -c y.tab.c
 lex babymake.l
 cc -c lex.yy.c
 cc -o babymake lex.yy.o y.tab.o babymake.o
$ ./babymake < babymake.example    
$ ./babymake < babymake.example bogus
ERRNO: 2: No such file or directory No rule to make target 'boguser'.
\$\endgroup\$
11
  • \$\begingroup\$ The program should take it's input from the standard input or by reading a file called "makefile" - is this a choice for the implementer to make? Or should the program read stdin, and if it's empty then look for makefile? Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error before execution of any rules. Does "generate an error" include aborting, such that no rules are executed? Running each in sequence - missing "action"? Why is the sample input indented? I'll do an edit for punctuation in a bit. \$\endgroup\$ May 20, 2011 at 21:36
  • \$\begingroup\$ In order. (1) Implementer's choice. Should be more specific. (2) Generate an error means abort; this is a unix utility after all. (3) The sample is indented because I made a strenuous effort to get the tabs in, and MarkDown just doesn't like tabs. Also there is a new sample input that has some comments in. \$\endgroup\$ May 20, 2011 at 21:49
  • \$\begingroup\$ More questions: 1) The target is "newer" than the prerequisite once *they* have been fulfilled. What does this mean? Should this text be talking about building? 2) Under what circumstances can a target be built twice? \$\endgroup\$ May 21, 2011 at 19:51
  • \$\begingroup\$ 1) Yes and 2) Standard make never builds a target twice, and neither does my reference implementation. But I should probably say that it is or is not allowed. Do you have a feeling in the matter? \$\endgroup\$ May 21, 2011 at 20:43
  • \$\begingroup\$ Saying that it is not allowed is probably best. Otherwise there's potential for stuff to go wrong when multiple targets depend on clean, which will never be built because it doesn't correspond to a file. \$\endgroup\$ May 21, 2011 at 21:15
  • 1
    \$\begingroup\$ I suggest that the golf exercise be to simply output the list of commands to run, not actually execute them. Will make testing much easier. \$\endgroup\$ May 27, 2011 at 0:50
  • \$\begingroup\$ This is awesome. But I'm too mystified by make to even fathom how it goes about it. I'd never be able to do this without stealing ideas from other posts on the page. But then, I'm an introverted intuitive, intellectuals would probbly have an easier time. :) I haven't checked, but .. I say it's ready to post. Answers may be slow in coming, but they WILL come! \$\endgroup\$ Nov 23, 2012 at 4:45
  • \$\begingroup\$ @luserdroog my reference implementation builds a directed graph (in the technical sense) of dependencies and then starts evaluating from the named target(s). I can't recall right off if I enforced acycality on the graph or not. I believe that real make insists on it. \$\endgroup\$ Nov 23, 2012 at 5:10
  • \$\begingroup\$ That doesn't semm quite so unfathomable. I suppose the variables and impicit rules are responsible for much of the mystery. \$\endgroup\$ Nov 23, 2012 at 5:45
  • \$\begingroup\$ This has been inactive for five years. If you're not going to post it, may I? \$\endgroup\$
    – MD XF
    Aug 17, 2017 at 16:59
  • \$\begingroup\$ @MDXF I think I'd rather post this one myself, but it may be a few days. \$\endgroup\$ Aug 17, 2017 at 19:51
4
\$\begingroup\$

BlackJack Part II

Repost from the original sandbox

As I had a blast working on the original KOTH challenge, I wanted to come up with another. For me, the fun of these AI challenges is in refining a comparatively simple bot which plays a very simple game subtly. Due to the probabilistic nature of card games, I think that blackjack could be an interesting KOTH game just like TPD.

Rules

  • Bots play at tables of four (4) competitors and one (1) dealer
  • One (1) shoe is shared by all players and the dealer until it is exhausted, at which point a new randomly shuffled deck will be added and play will continue. The bots ARE NOT (at present) NOTIFIED of the addition of this new deck. [TODO? would make card-counting a LOT harder...]
  • There is a buy-in of 10 per round, and cards are free
  • There is no bet maximum as bets are between the player and the house, yet the bot must have sufficient chips to immediately finance the bet.
  • Perfect/ideal hand has a score of 21
  • All face cards have a value of 10
  • All numeric cards are worth their number
  • Aces are worth 11 or 1. this will be dealt with automatically by the framework, not the bots.
  • Scores in excess of 21 which use an ace as 11 force the ace to reduce in value to 1 scores in excess of 21 which cannot be coerced below the threshold of 21 "bust" the bot
  • The dealer draws until he busts, or excedes a score of 17.
  • The stake is subtracted from chips, so the chips value is the number of credits which are available to the bot for betting.

Dealing and Bot Moves

  1. When the game starts, each player is iteratively dealt one card, and has the $10 buy-in fee/minimum bet subtracted from their chips.
  2. Then (in the same order as they were dealt to) each bot is executed as described in the "Programmer's Interface" section and must make a move or stand. Betting is considered a move. NOTE THAT BETTING DOES NOT AFFECT BOTS' ABILITY TO MAKE FURTHER MOVES. It is very possible to bet and then draw a card, and it is possible to draw multiple cards and them bet before standing.

Programmer's Interface and Legal Moves

As documented in the CardShark class:

#   DOCUMENTATION
#       INPUT SPECIFICATION
#          $ ./foo.bar <hand-score> <hand> <visible cards> <stake> <chips>
#          <hand-score>     is the present integer value of the player's hand.
#          <hand>           is a space-free string of the characters [1-9],A,J,Q,K
#          <visible cards>  every dealt card on the table. when new shoes are brought
#                           into play, cards drawn therefrom are simply added to this list
#                           !!! THE LIST IS CLEARED AT THE END OF HANDS, NOT SHOES !!!
#          <stake>          the  number of chips which the bot has bet this hand
#          <chips>          the number of chips which the bot has
#       SAMPLE INPUT
#          $ ./foo.bar 21 KJA KQKJA3592A 25 145
#
#       OUTPUT SPECIFICATION
#          "H"|"S"|"D"|"B"  (no quotes in output)
#          "H"              HIT - deal a card
#          "S"              STAND - the dealer's turn
#          "D"              DOUBLEDOWN - double the bet, take one card. FIRST MOVE ONLY
#          "B 15"           BET - raises the bot's stakes by $15.

Winner Selection

The winner would be the author of the bot which consistently accrued the most chips over a yet-to-be determined number of tables and rounds.

Code Review github

Issues & ToDo

None! (no known problems at least)

PS. How do I tag questions/answers? thanks @dmckee [ai-player] [card-game] [koth]

Version History

5/25 - 0020 - v1 - updated code on GitHub which fixes a bug with the dealer. DD still scores monstrously for unknown reasons. tagged this post (with any luck).

5/25 - 0800 - v2 - bugfix on github which correctly implements DoubleDown, resulting in drastically reduced scores from the double-nut bot.

5/25 - 0920 - v3 - updated the test case to match the input specification. Added the rules for the dealer.

5/25 - 1100 - v4 - added a description of the table and shoe system.

5/25 - 1620 - v5 - added an explanation of the betting and card-dealing system, major status update.

5/27 - 1700 - v6 - ready to roll the contest...

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Tags: [ai-player] and [card-game] seem naturals, though neither exists on the site as yet. What else? \$\endgroup\$ May 25, 2011 at 4:00
  • 1
    \$\begingroup\$ The SAMPLE INPUT isn't consistent with the INPUT SPECIFICATION - do the args include the current score or not? How many decks of cards should we assume to be used? Does <chips> include <stake>? How does the AI dealer play? Is each bot-dealer pair using a separate shoe (so that when I stand the dealers cards are drawn fairly from all those not included in <hand> and <visible-cards>)? When does betting occur? \$\endgroup\$ May 25, 2011 at 12:17
  • \$\begingroup\$ should players be notified of the number of decks in play, or not? The issue is that decks are dealt from until the deck is exhausted, then the "cannot pop from empty list" error signals the creation of a new shuffled deck then continues drawing as if nothing had happened. This means that multiple decks can be in play at once, but the statistical worst-case is that each player has three or four cards, which makes between fifteen and twenty samples split between two decks of 52. It shouldn't make a difference to score-based bots, but card-counters will need to detect or be notified of the chage \$\endgroup\$
    – arrdem
    May 25, 2011 at 15:16
4
\$\begingroup\$

Given a text, determine the language it is written in. The possible languages are: English, Danish, Romanian and Hungarian. The shortest program wins.

Some examples of text in each language can be found at Project Gutenberg

You are required to include examples of runs on text files other than the ones provided here.

The input file name is given as a command line argument. Except the input text, you are not allowed read additional files (e.g. to train your program) so please encode any data in your program.

Your program must output on of the following words English, Danish, Romanian, Hungarian.

Examples

$ ./language pg2600.txt
English
$ ./langauge pg12167.txt
Danish
$ ./language 11756-0.txt
Romanian
$ ./language 30163-0.txt
Hungarian
\$\endgroup\$
6
  • \$\begingroup\$ Another source of plain text passages might be the Gutenburg project. They do have books in languages other than English. \$\endgroup\$ Jun 22, 2011 at 14:53
  • \$\begingroup\$ Thanks. I updated the text problem to include some books from Gutenberg. \$\endgroup\$
    – Alexandru
    Jun 22, 2011 at 15:04
  • \$\begingroup\$ Related \$\endgroup\$
    – Beta Decay
    Sep 7, 2016 at 10:32
  • \$\begingroup\$ Looks pretty trivial to me. Any sufficiently long text will have ă if Romanian, ő if Hungarian, å if Danish, and neither if English. None of the special characters occur in any other of the four languages. \$\endgroup\$
    – Adám
    Jun 5, 2017 at 10:45
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$
    – user58826
    Jun 9, 2017 at 15:20
  • \$\begingroup\$ @programmer5000 The OP hasn't been seen since 2011, I think you're fine. \$\endgroup\$ Jul 21, 2017 at 13:21
4
\$\begingroup\$

How long until my next birthday is on a weekend

I would like to know how much time (in days) I have to wait (from now) until my birthday occurs on a weekend...

  • The required tool could accept arguments or standard input.
  • The only variable passed as input (as argument or stdin) is my birth day in the strict form YYYY/MM/DD with only digits, separated by / (of course: YYYY for birth year, MM for the month and DD for the day of month.
  • The output must present the number of days to wait, from now, and the target date with the day of week, in the form Wait DTW days to WWW, YYYY/MM/DD where DTW in integer is the number of days to wait, WWW as day of week abbreviation could be Sat or Sun and the target date in same form as input.
  • Once done, there is no more request (tool could finish quietly, loop, bug or crash)
  • About February 29th, there are 3 ways you can handle it:

    • strict: Where birthday may occur once every 4 years
    • right: Where birthday is March 1st while Feb 29th doesn't exist.
    • relax: Where birthday could be Feb 28th or March 1st, but only while Feb 29th doesn't exist.

    The tool must match in the right manner, but could accept an option as choice between one of the three ways.

  • Shortest golfed code wins
    • -3 explanation (while golfed version must use one letter variable, ungolfed version is welcome with useful variable names)
    • -3 if properly loop on STDIN
    • -5 if no requirement of external library
    • -10 if an option to choose the way of considering February 29th.
    • 0 for shebang (unless they contain more than runtime options: switch r in sed or p in perl are runtime options, they count for null)
    • N embed code on shebang line in counted normally.
\$\endgroup\$
7
  • 2
    \$\begingroup\$ How would you handle birthdays on February 29th? It would be an interesting special case, and it will increase the complexity of the problem. \$\endgroup\$
    – PhiNotPi
    Dec 13, 2013 at 23:15
  • 1
    \$\begingroup\$ Is this going to get answers which are much different to the currently active calendar-related questions? IMO it would be best left for a couple of months. Variety is a good thing. \$\endgroup\$ Dec 13, 2013 at 23:41
  • \$\begingroup\$ @PeterTaylor I'm not sure about what to answer to this. I think: yes in that: there is two input: current day and birthday, a range in week, not only one day and may different thinking may build different solution... \$\endgroup\$
    – F. Hauri
    Dec 14, 2013 at 9:34
  • \$\begingroup\$ @PhiNotPi Thanks, question edited! \$\endgroup\$
    – F. Hauri
    Dec 14, 2013 at 9:42
  • \$\begingroup\$ @PeterTaylor I've already browsed calendar questions ;-) \$\endgroup\$
    – F. Hauri
    Dec 14, 2013 at 9:46
  • \$\begingroup\$ Instead of listing this as code-golf, I recommend that you list it as code-challenge and change "Shortest golfed code" to "Lowest score" and add: 1 for each char \$\endgroup\$
    – Justin
    Dec 21, 2013 at 7:35
  • \$\begingroup\$ This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 15:39
4
\$\begingroup\$

3D Maze Navigation

Output a path through a 3D maze.

Input

The input will be from STDIN and will be a 3D maze. The maze will be input in slices horizontally across the maze starting from the top and moving down to the bottom. Each slice will be of the same width and depth, though the width, depth and number of slices could be different from run to run, and each slice will be separated by a blank line in the input. Here's an example:

*****
*****
*****
*****
*****

*****
*@* *
* * *
*   *
*****

*****
*** *
*****
*****
*****

*****
*>* *
* * *
*   *
*****

*****
*****
*****
*****
*****

The * character represents a solid wall or floor, @ is our hero and > is the exit from the maze.

Output:

The aim is to find if there is a way for the hero to get to the exit, and if there is, to show him the way with a series of directions:

SSEENNDDSSWWNN

Obviously this is a very simple maze, but the test cases will be harder than this. To complicate matters, the maze includes zero or more doors which can only be opened if the hero has picked up the correct key on the way. Each key is represented by a lower case character, and will only open a door represented by the uppercase version of the same letter (so a opens door A, b opens B and so on). The action of picking up a key is represented in the output with an X, and the hero has small hands and so can only hold one key at a time (his other hand is holding his mobile phone so he can keep track of his SO reputation). This may mean in some cases that he has to backtrack to get the next key required.

A couple of examples:

Input:

*****
*****
*****
*****
*****

*****
*@*>*
* *D*
*d  *
*****

*****
*****
*****
*****
*****

Output:

SSXEENN

The key and door have to be in the correct order, he can't use a key from beyond the door to open the door. If the maze has no solution, you should output nothing at all.

Input:

*****
*****
*****
*****
*****

*****
*@*>*
* *d*
*D  *
*****

*****
*****
*****
*****
*****

Output:

I'm providing a few test cases.

Test case 1

Input

******                ******
******                ******
******                ******
******                ******
******                ******
******                ******
******                ******
******                ******
******                ******
******                ******

******                ******
** * *                *    *
** b**                * ** *
** * *                * *  *
*  * *                * ****
* ** *                * *> *
*    *                * ** *
***A**                * ** *
*@   *                * *  *
******                ******

****************************
** * ***********************
****************************
**** ******************** **
****************************
****************************
****************************
****************************
**** ****************** ** *
****************************

****************************
** * *        *    **   *  *
** * * ****** * ** *  * * **
* B* *   *    * e* * ****  *
* **** * *c***** *   *   * *
*  **  * *    ** ***** **  *
**    ** ****  *        * **
*  *****C*** ** * *****E* **
*d**a***D             * *  *
****************************

****************************
****************************
****************************
****************************
****************************
****************************
****************************
****************************
****************************
****************************

Output (other solutions may exist, but I think this is the shortest)

EEEDDXUWNNWWNNENNEXWNDDSSWSSESEEENENNNNEEEEEEESSWWWSXNEEENNWWWWWWWSSEESSSSNNNNWWSSWSWWWSWSXNENEEENENNEESSSSSEEEEEEEEENNWNNNXSSSEEEEEEESSUUNNNNNNNEEESSWDDESSWSSSEUU    NNNW    
\$\endgroup\$
16
  • \$\begingroup\$ If W puts out F and K opens D, who specifies that? Maybe you could go abstract and say that A unlocks a, B unlocks b... \$\endgroup\$ Dec 23, 2013 at 13:09
  • \$\begingroup\$ @JanDvorak The pairs of obstacles and equipment need to overcome them would be specified in the question. At the moment I'm trying to see if that's a complication too far and if I should stick to the easy version of the challenge (I think I'd prefer to post the harder version, but there's no point if no-one would answer it). \$\endgroup\$
    – Gareth
    Dec 23, 2013 at 14:08
  • \$\begingroup\$ I don't mind keys and doors (somehow I like the extra challenge), but memorizing a {char x char} lookup table doesn't really serve anything. \$\endgroup\$ Dec 23, 2013 at 14:10
  • \$\begingroup\$ @JanDvorak Okay, that's a fair point. \$\endgroup\$
    – Gareth
    Dec 23, 2013 at 14:11
  • 1
    \$\begingroup\$ On that same note, I suggest using non-alphanumerics for the hero and exit. You can get inspired by the rougelike genre: @ means the hero, and > means "stairs down" (exit). Or, you could use < (stairs up) for the starting point. Then the path/non-path would be dots (lit floor) vs. spaces (unlit floor). \$\endgroup\$ Dec 23, 2013 at 14:15
  • \$\begingroup\$ Is the solid border guaranteed? \$\endgroup\$ Dec 23, 2013 at 16:42
  • \$\begingroup\$ Yes. There will be a a solid border to each side and above and below. There will be no way to escape the maze in any of the test cases. \$\endgroup\$
    – Gareth
    Dec 23, 2013 at 16:43
  • \$\begingroup\$ Also, what if there are multiple paths? Which path should we choose? \$\endgroup\$ Dec 23, 2013 at 16:44
  • \$\begingroup\$ For the purposes of providing test scripts, I'd probably ensure that there was only one possible path in the tests. Maybe I should add a guarantee that that would be the case in the question? \$\endgroup\$
    – Gareth
    Dec 23, 2013 at 16:51
  • \$\begingroup\$ Without the keys this is just another shortest path question, so I think the keys are essential to make it interesting. However, they potentially lead to routes which double back on themselves, and the output format doesn't handle this well. What do you think to changing the output to a string of e.g. NSEWUD? \$\endgroup\$ Dec 24, 2013 at 7:58
  • \$\begingroup\$ @PeterTaylor I thought the 3D aspect might make it more interesting than another shortest path question? Yes, I'm very flexible on the output format. My biggest worry is making the test cases such that there is only one possible correct answer to make it easy for me to modify the test scripts that I already use. \$\endgroup\$
    – Gareth
    Dec 24, 2013 at 10:14
  • \$\begingroup\$ 3d changes the lattice structure slightly but IMO it's a trivial change. The keys add a dimension each. To help the unique solutions you could prohibit doubling back, so that each step adds a dimension and steering AI is necessary to keep performance acceptable. \$\endgroup\$ Dec 28, 2013 at 10:08
  • \$\begingroup\$ @PeterTaylor Is it better to prohibit doubling back or maybe only allow the holding of one key at a time (requiring doubling back to get the correct key in some cases)? \$\endgroup\$
    – Gareth
    Dec 30, 2013 at 22:52
  • \$\begingroup\$ Holding one key at a time increases the state space moderately (I make it a factor of n * 2^n), but I expect answers would still be straight Dijkstra. It adds a complication which should be clarified: if I'm carrying a key, am I prohibited from stepping on a different key, or do I pass over it and leave it alone? \$\endgroup\$ Dec 31, 2013 at 8:33
  • \$\begingroup\$ @PeterTaylor If I was to take that path you would be able to pass over keys without picking them up. \$\endgroup\$
    – Gareth
    Dec 31, 2013 at 9:46
4
\$\begingroup\$

4 and 20 baked in a π

While some might describe π as a string of seemingly random numbers, one can also look at it in a way similar to a monkey with a typewriter. Eventually, it should calculate out to something more interesting. For example, the sequence 1337 shows up 4,814 places to the right of the decimal. At 700,731 places right of the decimal, you'll find the sequence 160151, which is "pi" represented as ASCII (although you'll find a 'pointer' to it much faster, as the sequence 700731 begins at 29,830 digits to the right).

So, your task is to make a program to find things in π. Your program will accept a positive integer and output the number of places right of the decimal point that number appears. To keep the run times down, input can be limited to numbers in the range of 0 to 1000 (without leading zeros).

Example: Using 415 as the input, the output should be 2:

3.14159
   ^

Rules:

  • You can not use any precalculated values of π, including language constants, built in functions that return π or digits of π, or any resource outside the code itself (such as files or websites).
  • You can not use any trig functions to calculate π.

Bonus points if you find the sequence 072 101 108 108 111 044 032 087 111 114 108 100 033.

This is code golf, so lowest score wins.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ It's not clear to me whether you require answers to support leading zeroes. Also: program, named function or snippet? And how indexed? (Giving 415 as a test case would be a good way to answer the last question) \$\endgroup\$ Mar 11, 2014 at 6:58
  • 3
    \$\begingroup\$ Isn't this just Calculate 500 digits of pi with a search function tagged on at the end? By the way, your bonus points are quite safe — even if you searched a trillion trillion trillion digits of pi, your chance of finding an arbitrary 39-digit sequence would still be less than 0.1%. \$\endgroup\$
    – r3mainer
    Mar 11, 2014 at 14:59
  • \$\begingroup\$ Edited to clarify leading zeros and indexing. @squeamishossifrage - Yes and no. The number of digits to find the answer depends on the input, which both limits the choice of algorithm to generate the search space and gives more ample room to golf the integration of the search function. The worst case is under 10000 digits for n between 0 and 1000. I suppose I could put in a time limit of a couple minutes and expand the range of n to 10000 (worst case is just under 390k), but that seems obnoxious. Thoughts? \$\endgroup\$
    – Comintern
    Mar 11, 2014 at 17:20
  • 1
    \$\begingroup\$ @AlexA. - Not a drug reference. \$\endgroup\$
    – Comintern
    Apr 1, 2015 at 22:34
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:15
4
\$\begingroup\$

ASCII ART edge detection

As the title says, I was thinking to contest in which one must detect edges of an ASCII art.

The code should accept a B/W ASCII art as input. A B/W ASCII art is defined as (by me) an ASCII art with only one kind of non-white-spaces character (in our case: an asteriks *). And as output produce a standard ASCII art (all ASCII characters are accepted) which should remember the contourn of the first.

The purpose of using more than one character in the output is to make some edges ssmoother. For instance, one could let this input

     *** 
   ****
 ******
******
****** 
 ******
   ****
     ***

could became:

      ___
    _/   ) 
  _/    /
 /      |
|      /
|      \
 \      |
  `\     |
     \___)

The input \n separated string as input. Each line has a maximum of 80 characters. The number of rows is not specified.

I'd put it as a popularity-contest since, beside my simple code, I'd like to see more "round" edge detections which use more than one character in smooth edges.

Also, I don't want to tag it as code-golf since I'm quite sure one can do this job using aplay (with ASCII art renderer) and command line GIMP (to apply edge detection).

As a popularity contest, there are no strict rules on how the output should be..just use your fantasy!

This is my sample program:

import fileinput as f
import re as r
import copy as c
a,s,p='*',' ','+'
def read(n):
    s=[list(' '*n)]
    for l in f.input():
        if(len(l)>n):l=l[:n]
        k=list(r.sub('[^ ^\%c]'%a,'',' '+l+' '))
        s.append(k+[' ']*(n-len(k)))
    s.append([' ']*n)
    return s
def np(s):
    s=c.deepcopy(s)
    for l in s[1:-1]:
        for w in l[1:-1]: print(w,end='')
        print()
def grow(i):
    o=c.deepcopy(i)
    for x in range(1,len(o)-1):
        for y in range(1,len(o[x])-1):
            if(i[x][y]==a): o[x-1][y-1]=o[x-1][y+1]=o[x-1][y]=o[x+1][y]=o[x+1][y-1]=o[x+1][y+1]=o[x][y+1]=o[x][y-1]=a

    return o
def diff(i,o):
    c=[]
    for x in range(0,len(i)):
        l=[]
        for y in range(0,len(i[x])):
            if(i[x][y]==a and o[x][y]==s): l.append(p)
            else: l.append(s)
        c.append(l)
    return c
I=read(80)
np(diff(grow(I),I))

Here below I put both input of the programs. It is an 80x70 ASCII ART. It means it has 70 lines of 80 characters, each separated by \n.

                                              *************
                                          *****          *****                   
                                     ******                  ***                 
                                    ***                         ****             
                             *********                             **            
                          ***********                               **           
                     ******   *******                                **          
                 *****       *******      ***                         **         
              ****          ********     *****                          *        
             **            *********     *****                    *****  *       
           ***            *********     *******                  ******  **      
          **             **********     *******                  ******   **     
         **              **********    *******                  ********   *     
        *               ***********   ******                    ********   *     
       **              ************   *****                     ********    *    
       *               ************    ***                       ********   *    
      *               *************                               ******    *    
     *                *************                                 ***     *    
    **                *************                                         *    
    *                **************                                         *    
   **                *************                                         **    
   *                 *************                                         **    
  **                *************                                          ***   
 ***                *************                                          ****  
 **                 ************                                           ****  
 **                *************                                           ****  
 **                *************           *****                           ****  
 **                *************          **   **          **              ****  
 **                 ************          *     *         ** **            ****  
 *                  ************          **   **        **   **           ****  
 *                  *************        *******         **   ***          ****  
 *                  ************          *****           *******          ****  
 *                   ************         ***               *****          ****  
**     *             *************                          ****          *****  
**    ***            **************                                      *****   
*    *****            *************                                     ******   
** *******             **************                                  *******   
**********             ***************              *                *********   
**********              *****************          ***             ***********   
***********              *******************                    **************   
***********               **********************            ******************   
************              *****************     **     ***********************   
*************             ******************      ****     *******************   
**************            ******************              ********************   
****************           ******************              *******************   
***************           *******************              *******************   
****************           ******************              ******************    
******************         ******************             *******************    
*******************         *****************             *******************    
*********************      ******************           ********************     
*********************************************          *********************     
**********************************************       ***********************     
************************     *****************      ************************     
 **********************       ******************* **************************     
 *********************        *********************************************      
 *********************        ****************************  ***************      
 ********************         **************************    ***************      
 ********************         *********************         ***************      
 *******************          ********************         ****************      
 ******************           *****************            ****************      
 *****************             ****************            ***************       
 *****************             ****************            ***************       
 *****************             *****************           ***************       
  ****************             *****************           ***************       
   **************              ******************          ***************       
                                 ****************          ****************      
                                  **************            ***************      
                                                             **************      
                                                              ************       

A possible output could be:

                                         +++++             ++++
                                    ++++++     ++++++++++     +++
                                   ++      +++++        +++++   +++++
                            ++++++++   +++++                ++++    ++
                         ++++         ++                       ++++  ++
                    ++++++           ++                           ++  ++
                +++++      +++       +   +++++                     ++  ++
             ++++     +++++++       ++  ++   ++                     ++  ++
            ++    +++++   ++        +   +     +                  +++++++ ++
          +++  ++++      ++         +  ++     ++                ++     ++ ++
         ++   ++        ++         ++  +       +                +      ++  ++
        ++  +++         +          +  ++       +               ++      +++  +
       ++  ++          ++          + ++       ++               +        +++ +
      ++ +++          ++           + +      +++                +        + + ++
      +  +            +            + +     ++                  +        ++++ +
     ++ ++           ++            + ++   ++                   ++        + + +
    ++ ++            +             +  +++++                     ++      ++ + +
   ++ ++             +             +                             +++   ++  + +
   +  +             ++             +                               +++++   + +
  ++ ++             +              +                                      ++ +
  +  +              +             ++                                      +  +
 ++ ++             ++             +                                       +  ++
++  +              +             ++                                       +   ++
+   +              +             +                                        +    +
+  ++             ++            ++                                        +    +
+  +              +             +         +++++++                         +    +
+  +              +             +        ++     ++        ++++            +    +
+  +              +             +        +  +++  +       ++  +++          +    +
+  +              ++            +        + ++ ++ +      ++  +  ++         +    +
+ ++               +            ++      ++  +++  +      +  +++  ++        +    +
+ +                +             +      +       ++      +  +++   +        +    +
+ +                +            ++      ++     ++       ++       +        +    +
+ +   +++          ++            ++      +   +++         +++     +       ++    +
  +  ++ ++          +             ++     +++++             +    ++      ++     +
  + ++   ++         +              +                       ++++++      ++     ++
 ++++     +         ++             +++                                ++      +
  +       +          ++              ++            +++              +++       +
          +           +               ++++        ++ ++           +++         +
          ++          ++                 ++++     +   +        ++++           +
           +           ++                   +++++ +++++    +++++              +
           ++           ++                      +++   ++++++                  +
            ++           +                 +++++  +++++                       +
             ++          +                  +  +++    +++++                   +
              +++        +                  ++   ++++++  +                    +
                +        ++                  +           ++                   +
               ++        +                   +            +                   +
                +++      ++                  +           ++                  ++
                  ++      +                  +           +                   +
                   +++    ++                 +         +++                   +
                     ++++++                  +        ++                    ++
                                             ++     +++                     +
                                              +    ++                       +
                        +++++                 ++++++                        +
+                      ++   ++                   +                          +
+                     ++     +                                             ++
+                     +      +                            ++               +
+                    ++      +                          ++++               +
+                    +       +                     ++++++ ++               +
+                   ++       +                    ++      +                +
+                  ++        +                 ++++       +                +
+                 ++         ++                +          +               ++
+                 +           +                ++         +               +
+                 +           +                 +         +               +
++                +           +                 ++        +               +
 ++              ++           +                  +        +               ++
  ++++++++++++++++            +++                +        +                +
                                ++              ++        ++               +
                                 ++++++++++++++++          ++              +
                                                            ++            ++
                                                             ++++++++++++++

This is also the output produced by the script above. Of course it is not the best output and I'm sure one can easily produce a smoother one.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ It would be useful to be more precise about which characters should be non-blank in the output: characters which were non-blank in the input but adjacent to blanks, or characters which were blank in the input but adjacent to non-blanks? \$\endgroup\$ Apr 4, 2014 at 9:50
  • \$\begingroup\$ Thanks for pointing. I re-written the phrase in the answer. You can use every ASCII character in the output (as usual ASCII art). E.g. I used only + symbol, but one could makes round edges using symbols like \ or / etc.. \$\endgroup\$ Apr 4, 2014 at 9:55
  • \$\begingroup\$ edited again... \$\endgroup\$ Apr 4, 2014 at 10:09
  • \$\begingroup\$ Can you define the input that will be used by all the participants? It's necessary to have only one input to compare the outputs of the different answers. The first example is too simple and the last one is too long. So I suggest to use something between these 2 examples. \$\endgroup\$
    – A.L
    Apr 4, 2014 at 17:29
  • \$\begingroup\$ Thanks, I chosen a cute panda as input. \$\endgroup\$ Apr 6, 2014 at 8:09
  • 1
    \$\begingroup\$ one could let this input (…) could became → try something like "this input (…) could become" outpuit → output \$\endgroup\$ Apr 7, 2014 at 13:31
  • \$\begingroup\$ I edited it now, so do you people thinks it is a good question? \$\endgroup\$ Apr 9, 2014 at 17:15
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:32
  • \$\begingroup\$ Hi @programmer5000 , I already asked such a question. Do you mean to re-use it again? See: codegolf.stackexchange.com/questions/26139/… \$\endgroup\$ Jun 12, 2017 at 13:39
4
\$\begingroup\$

Find sociable numbers

Background

A number is perfect if it is the sum of its divisors; for instance 6=1+2+3

A pair of numbers is friendly if they are the sum of each other's divisors; for instance 284=1+2+4+5+10+11+20+22+44+55+110 and 220=1+2+4+71+142.

In general, a list of n numbers is sociable if each element is the sum of divisors of the previous elements, with the first being the sum of divisors of the last.

Input

An integer, n on STDIN.

Output

A list of n numbers which are sociable, in the order outlined above, each on its own line. If you can't find any suitable list, you may output nothing, False, or 0, but you must search up to at least 2^32-1, and preferably as high as your language will allow

Winning

This is code-golf, so the shortest code wins. However, I will also create a bounty to be awarded to the fastest program, as measured on my command-line (Windows 7 with GNU coreutils, python27, python3, node.js, perl) or in a web IDE in chrome (brainfuck, golfscript?)

Edit: to clarify the relationship between input and output

\$\endgroup\$
7
  • \$\begingroup\$ The relation between the input and output is unclear. Are we asked to find the loop of sociable numbers that the input number leads to by iterating "sum of proper divisors"? \$\endgroup\$ Apr 19, 2014 at 11:17
  • 1
    \$\begingroup\$ @JanDvorak, no, we're asked to find a cycle of length n in the directed graph whose vertices are the natural numbers and whose edges are i -> aliquot_sum(i). \$\endgroup\$ Apr 19, 2014 at 19:09
  • 4
    \$\begingroup\$ I don't think it's a good idea to have a code golf and a fastest code challenge in the same problem. You'll get incomparable answers. Maybe make a composite score that incorporates time and length? \$\endgroup\$
    – isaacg
    Apr 21, 2014 at 0:58
  • \$\begingroup\$ That may be better. \$\endgroup\$ Apr 21, 2014 at 21:08
  • \$\begingroup\$ Would you allow the usage of predefined functions that calculate the aliquot sum? \$\endgroup\$
    – Wrzlprmft
    Apr 22, 2014 at 13:49
  • \$\begingroup\$ @alexander-brett Are you going to post this? \$\endgroup\$
    – Oliver Ni
    Oct 9, 2016 at 4:28
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:38
4
\$\begingroup\$

Save your job in QA!

You work for a software company's QA department, writing automated acceptance tests for their products. One day, your boss calls you in to his office, and to your astonishment tells you that your entire department is being "rationalized".

"But why?" You ask

"One of the fellows in development told me about these new-fangled things called 'unit tests'. Apparently, you can test each little bit of code as you write it. And since the developers do it themselves, that means we don't need a QA department any more."

You hesitate. "Well unit tests are a good idea, but you still need-"

"Nonsense!" Your boss blusters, cutting you off mid-sentence "If we can test every little bit of the code, we don't need to test the whole lot again!"

Your boss is adamant, but after a bit of wrangling, he grants you one chance: later that day, you will present him with a demonstration proving that unit tests alone aren't enough to test your product.

The challenge

Your challenge is to write the following:

  • A system under test with more than one part
  • Unit tests for each part
  • One or more integration tests, consisting of multiple parts working together

The unit tests should appear to prove that the system under has one behaviour, while the integration tests should prove that it actually has another.

Guidelines

This is a popularity contest, and the following criteria should be taken into account for rating the answers:

  • The trick leading to the unit tests having different conclusions to the integration tests should be primarily in the system under test. Your boss won't be impressed if all you did was insert a bug into one of your tests!
  • The more convincingly the individual unit tests and integration tests appear to prove what they are each attempting to test, the better.
  • The more convincingly the conclusions of the integration tests appear to contradict the unit tests, the better. For example, an answer where both the unit tests and integration tests use the same inputs to the system under test would probably be better than one that relies on them using different inputs. An answer where the integration test tests some behaviour of the system which was clearly not covered by the unit tests would also not be a very good answer.

Tests may be written in whatever format is appropriate for the language you are using. Two possibilities which would work in many situations would be:

  • Tests have no return value, but throw an exception (or equivalent) if they fail
  • Tests return true for a pass or false for a fail
\$\endgroup\$
4
\$\begingroup\$

Cube puzzle

Write a program that can determine whether or not a collection of puzzle pieces can be assembled to form a solid cube. The pieces can be moved and rotated, but not reflected.

Each puzzle piece consists of a connected set of sub-cubes. The arrangement of these sub-cubes is described an ASCII representation consisting of a single line with three space-separated numbers x, y and z, followed by z blocks of x × y characters where X represents an occupied sub-cube, and . represents an empty sub-cube. The first line of input indicates the number of puzzle pieces that follow (N).

Input/output:

Your program should accept input from stdin, and should print its results to stdout. If the pieces can form a cube, it should output the line "CUBE". If not, it should output "NOT A CUBE".

Example:

enter image description here

In the above illustration, a 3×3×3 cube is constructed from five pieces. If the pieces are listed in the order {pink, yellow, blue, red, green}, then the input could look something like this:

5
3 2 1
X..
XXX
3 2 2
XXX
X..
...
X..
3 3 2
...
.X.
...
XXX
.X.
XX.
2 3 1
XX
XX
.X
3 3 2
X..
X..
X..
...
...
XXX

Limits:

Your program should be able to handle any puzzle comprising up to 10×10×10 sub-cubes.

Winning criterion:

This is a challenge. The shortest answer (measured in bytes of code) will win.

\$\endgroup\$
8
  • \$\begingroup\$ This is a nice idea but the input format seems complicated. I have another idea: use directions to define the pieces. For example for the pink piece: .RRU (start, then go to Right twice then go to Up). Directions are Up, Right, Dowm, Left, Front and Back. \$\endgroup\$
    – A.L
    Jun 25, 2014 at 21:42
  • \$\begingroup\$ OK, but how would that work for pieces that contain branches (like the blue one, for example)? \$\endgroup\$
    – r3mainer
    Jun 26, 2014 at 14:37
  • \$\begingroup\$ Ah, I forgot this case. :-) I think we can use a direction to get back from the branch to the trunk. For example for the blue one: .RTTBFTLRR (the point is view is located at the left of your image) \$\endgroup\$
    – A.L
    Jun 27, 2014 at 2:44
  • 1
    \$\begingroup\$ @A.L what does T signify? \$\endgroup\$
    – trichoplax
    Jul 19, 2014 at 21:21
  • \$\begingroup\$ @githubphagocyte oops, I wrote T for Top, it's U instead. \$\endgroup\$
    – A.L
    Jul 19, 2014 at 23:06
  • 1
    \$\begingroup\$ @A.L so .RUUBFULRR? Makes sense now thank you. \$\endgroup\$
    – trichoplax
    Jul 19, 2014 at 23:22
  • 1
    \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:53
  • \$\begingroup\$ @programmer5000 You're welcome :-) \$\endgroup\$
    – r3mainer
    Jun 10, 2017 at 21:41
4
\$\begingroup\$

Paired Programming: Down Periscope!

This is very basic for now, and lacks specific numbers as I flesh out the details and play with the speeds involved. I/O will be pretty basic, but it's not fully outlined yet.

Four submarines are placed in an arena, two on each team. They shoot torpedoes at each other. The objective, as obvious as it seems, it to kill the opposing team.

Teams are made from all pairwise matches of entries. They are then placed in a tournament-style bracket, deep enough to fit all of them. Any empty spaces are filled with a team of two dummy submarines, effectively creating a bye assuming you don't lose to a team that quite literally can't kill you.

The tournament is played several (many?) times to tally points. The team with the most points at the end is the winning team. In the interests of selecting a single winner, the winning team's bots will be compared. Whoever got the most points total (even from their participation on other teams) is the overall winner. Note that this means the single bot with the most points may not win (due to not being on the winning team).

Sensors down, Captain

Unfortunately, you've lost most of your communications ability, and your navigation sensors are limited. Specifically, you have two ways to figure out what's around you and/or communicate: passive and active.

  • Passive Audio: Since water is such a great conductor of sound, you can hear things from a pretty good distance. Of course, today's submarines can run pretty quietly, but as they speed up, they get louder. You can also hear other things, like active torpedoes, explosions, and sonar pings. For each of these events, you will receive a bearing (azimuth/elevation) and a loudness. Loudness drops off with distance, so you may not be able to hear everything in the arena. You don't have to directly ask for this information, it will be supplied on each turn.

  • Active Sonar: When that just isn't good enough, there's sonar. When you activate a sonar ping, you will receive a bearing and distance to all objects (submarines/torpedoes). Of course, other subs will also be able to hear you when you do.

(Tentative) As a bonus, you can modulate a short message onto the sonar ping to communicate with other subs. This message can be up to 16 bytes in length. Just remember, all other subs will be able to hear this message, not just your teammate. They will hear it as an addition to the ping during passive listening. If you have idea about how to make this useful/effective, I'm usually available in chat.

Take us down

Movement is based on vectors, and any movement commands you give are applied. Acceleration is a fcator in speed and direction, so you can't go from full stop to all out in one step. To move, you need three values: left/right, up/down, and throttle.

  • Left/Right: Supplied in absolute degrees from north. There is a maximum turn rate, so the ship will slowly come about to face the new heading. If the value is out of the bounds 0<=d<=359 it will be modulus 360. The ship will turn in whichever direction would result in the shorter turn, so if you want to make a 270-degree clockwise turn from north, you'll need to do it in increments of something <= 180. If you set a heading exactly 180 degrees from current, it will turn clockwise.

  • Up/Down: Supplied in absolute degrees of the desired angle. The ship will slowly come to the desired angle. Min/max to be determined.

  • Throttle: Supplied in meters/second desired speed. The ship will accelerate at a rate of (TBD) until desired rate is achieved (up to maximum of TBD). You cannot move backward(negative speed). This makes noise! The faster you are moving, the louder your sub is.

Fire torpedoes!

You have two torpedo tubes, and an unlimited supply of torpedoes. When you fire one, it will take some time to reload, so your effective firing rate is 2/x(tbd) seconds. You don't have to specify which tube you're firing, the command will fire whichever is ready.

Torpedoes start off moving at the sub's current speed plus a small boost (to prevent detonation with firing sub). It then accelerates up to full speed. Torpedoes **home in* on any sub within their cone of vision, and will try to turn to hit whichever of these is the closest. Although a torpedo's max speed is higher than a sub's, it cannot turn as quickly, so evasive maneuvers need to be considered.

Torpedoes have distance sensors, and will blow up when they are within x(tbd) meters of a sub. This will destroy the sub, and be very audible. Torpedoes have a maximum travel distance of (tbd) meters, at which point they fizzle out and are no longer a hazard.

The Arena

The arena is a spherical area of ocean with the origin at the center and a radius of 1000m(?tbd). Coordinates are continuous. Subs will start near the perimeter, at 90 degree intervals around the equator. They will start facing the center, with teammates 180 degrees apart. Moving outside the sphere is death, and will be audible.



Now obviously I've still got some work to do here, but as usual any comments are welcome. Well, most comments are welcome.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ How does the movement work? Angle adjustments applied first and then a single linear step? (Making sure that everyone can easily predict their own position is essential to not having people complaining that they didn't move outside the sphere). \$\endgroup\$ Aug 7, 2014 at 22:13
  • \$\begingroup\$ @PeterTaylor Yes, turns both horizontal and vertical applied before the step forward. On that note, I've thought about getting rid of the sphere and making it toruslike, but I'm undecided. \$\endgroup\$
    – Geobits
    Aug 7, 2014 at 22:22
  • \$\begingroup\$ I think that making it wrap (which I assume is what you mean) would be a conceptual headache when it comes to interpreting pings and trying to integrate longitudinal data. \$\endgroup\$ Aug 7, 2014 at 22:25
  • \$\begingroup\$ @PeterTaylor Agreed, that's why it's a sphere as it is. If I could think of a good way to do it without making the boundary insta-kill, though, I would. Just avoiding the walls might be enough to put some people off, since turns aren't instant and you have to figure out your turn radius from your current speed. \$\endgroup\$
    – Geobits
    Aug 7, 2014 at 22:28
  • \$\begingroup\$ One way would be to introduce a speed limitation beyond the boundary, but that would require very careful explanation to ensure that everyone's simulations agree. (Actually, on the subject of simulations agreeing: you might need to say something about using strictfp in languages like Java). \$\endgroup\$ Aug 8, 2014 at 8:38
  • \$\begingroup\$ One possibility for the boundary: Instead of killing you it just prevents you from moving outside it and makes a loud noise when you bump into it or scrape along it. \$\endgroup\$
    – trichoplax
    Aug 10, 2014 at 19:52
  • \$\begingroup\$ Instead of making the boundary itself insta-kill you could just surround the arena with mines which increase in density the farther away from the center you travel. \$\endgroup\$
    – ccarton
    Aug 25, 2014 at 12:58
4
\$\begingroup\$

Realistic Stock Market

This is based off of this other challenge, but with a whole lot of added realism. I'm trying to add as much realism as possible. It is a challenge.

You are an entrepreneur in the stock market, having created your own hedge fund (correct term?). Your company buys and sells shares in other companies, but also sells shares in itself.

At the very end of the game, the money is redistributed: All the money you've earned* is split up amongst your shareholders. Likewise, you gain money from the companies in which you've invested. By selling shares in yourself, there is a trade-off between long- and short-term gains.

There is a finite amount of each stock in the game, and there is one type of stock per company (so one per entrant). Your bot will start out with 100 shares of each other company, along with 100*N shares of itself, where N is the number of entrants. Each bot will have an initial bankroll of 10000 * N. (This helps to ensure a sufficiently large initial stock price).

Buying and Selling

Buying and selling stock is done by placing buy and sell orders. Each time a buy/sell order is placed, it is matched with the existing buy/sells orders to complete the trade.

Here is an example of how the orders are matched with each other for one stock:

 Before:
  Sell Orders:
   19 @ $20 - Bot A
   11 @ $21 - Bot B
  Buy Orders:
   06 @ $19 - Bot S #oldest is given preference 
   06 @ $19 - Bot Q
   13 @ $18 - Bot T
   22 @ $16 - Bot R

 New Order:
  Sell 26 @ $17 - Bot C
  Trades [06 @ $19 - Bot S] with a surplus of 20
  Trades [06 @ $19 - Bot Q] with a surplus of 14
  Trades [13 @ $18 - Bot T] with a surplus of 01
  No more matches

 After:
  Sell Orders:
   01 @ $17 - Bot C #the remainder of the sell order
   19 @ $20 - Bot A
   11 @ $21 - Bot B
  Buy Orders:
   22 @ $16 - Bot R

In this particular example, Bot C will manage to sell 26 shares for 12*19+13*18+1*17 = $479, assuming that someone will eventually buy that one remaining share. The bot receives $462 at the end of his turn, and would receive the $17 at the end of the buyer's turn. If the share is not bought in the time between one turn and the next, the bot would receive that remaining share back.

The Tournament Setup

The tournament will be composed of 10 games, with each game consisting of 365 trading rounds. Each trading round will consist of one turn for each bot, with the bots in a randomized order.

There is nothing special that happens between any particular round. This helps to smooth out game flow so that each bot will have equal opportunity on their turn.

At the end of each game, the money of each competitor is redistributed to its stock holders (how much of the money?).

The winner of the tournament will be the bot with the highest average amount of money at the end of each game.

A Single Turn

For each stock, the bot will receive the buy and sell orders available.

At the start of every bot's turn, that bot's previous unfulfilled sell/buy orders will be canceled. (Is this a good idea?). Any unsold stock or unspent money is returned to the player.

Then, the bot will output the list of buy/sell orders it would like to place. The bot will be able to place one buy/sell order per stock. The bot must be able to immediately set aside the shares/money to support the order.

The controller program will look through your sell and buy orders sequentially and will remove the assets from you that are required for the transaction. If you have insufficient funds, that order will be ignored completely.

Then, the orders will be processed. Orders that match the already-existing orders will allow the transaction to occur after the bot's turn. Orders that are unmatched will remain on the market until the start of the bot's next turn.

Recording the past

Your bot is allow to create 1 text file to maintain a history of stock prices.

Input

Input will consist of 3 arguments in this order:

Current round number, which is a number 1-365
Which stock ticker is for your company
A list of the data for each stock

The data for the stocks will be formatted like this:

"[stock ticker #1],[quantity 1],[price 1],[quantity 2],[price 2] [stock ticker #2],[quantity 1],[price 1],[quantity 2],[price 2]"

Each quantity/price pair represents one buy or sell order. Sell orders have positive quantity, while buy orders have negative quantity.

The order of the stocks will be randomized, but the stock tickers will remain consistent for the whole game.

(I was also think of including some more data in here, what else might be needed? Data on the assets of all the other competitors?)

Output:

Output will consist of many lines, each line formatted like so:

[stock number 1-N] [action] [quantity] [price]

The stock number is a number 1-N representing which stock to buy or sell. The action can be either b for buy or s for sell. The quantity and price can be any positive integer.


Notes:

I want price to have 2 decimal digits, but I don't know if that would exclude anything or make it unnecessarily complicated. Right now, the prices are limited to integers. There is approximately $50 for each stock in the game, in an attempt to increase smoothness.

We need to balance the number of actions allowed per turn with the number of rounds in a game. Right now, the player can make 1 order per stock in a single round, which may make the time flow too roughly. The more rounds played, and the fewer actions allowed per turn, the smoother the game will be.

*We need to determine exactly how the money is redistributed. I initially had the idea that all the money will be redistributed equally to each stock, so a player who sells all the shares in himself keeps none of the money he earned in game and only gets the money from the other stocks. I think it might make more sense to only distribute profits, but we would have to determine how much of the profits are redistributed to shareholders.

Is it a good idea to have orders cancel after a period of time? Currently, a bot's orders are cancelled upon that bot's next turn. If we reduce the number of moves per turn, then we would want to increase the longevity of the orders. Alternatively, we could make orders permanent and irrevocable, only being cancelled at the end of the game.

\$\endgroup\$
11
  • \$\begingroup\$ If you give priority to orders that are older, then it makes sense to let orders persist beyond one turn. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:07
  • \$\begingroup\$ Alternatively you could give priority to larger orders, in which case the priority would not affect your decision on whether to cancel orders after one turn. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:08
  • 1
    \$\begingroup\$ The number of decimal places is largely irrelevant - a fixed number of decimal places is equivalent to integer. It's probably easier to model as integers internally, even if you display as 2 decimal places. You could just state that prices are in pennies/cents. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:10
  • \$\begingroup\$ If a bot is limited in the number of buy and sell orders it can place by its available funds and shares, then that might be enough. If someone does decide to place a buy order on every single company, that will mean spreading their funds thinly as they cannot place buy orders that sum to more than the cash they have available. This naturally limits the activity level each turn. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:14
  • 2
    \$\begingroup\$ I would recommend allowing orders to be placed and cancelled at any time. I don't think a restriction is necessary. What might make it more interesting is to introduce a cost to buying and/or selling. This should make strategy more important. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:16
  • \$\begingroup\$ Costs could be of two types: a percentage commission on each successful sale or purchase, and also a fee for placing or cancelling an order. So bots will have to weigh up their options - to cancel an order they are uncertain they still want or leave it open to avoid a fee. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:18
  • \$\begingroup\$ There's also a big decision to be made on how the market works. At present the prices are based purely on speculation of what those same prices will be in future. The alternative is to also have some non-player companies modelling companies selling products rather than just investing. Say 4 companies, one each for flour, eggs, rice and treacle. Those companies pay out dividends based on the randomly varying company profit, then bots use that income to pay out dividends based on how well they did out of the companies they are invested in. \$\endgroup\$
    – trichoplax
    Aug 14, 2014 at 18:24
  • 1
    \$\begingroup\$ I think that making each bot specify up front how much it will pay out in dividends would be good. It adds some asymmetry in round 1 (so it's not just picking a random share to buy). Probably do it in integer permille and round down when the time comes to distribute. It might even be interesting to make dividend payouts quarterly so that they don't just affect the final score. \$\endgroup\$ Aug 14, 2014 at 19:43
  • \$\begingroup\$ I'd like to see the dividend percentage able to be changed, so that bots can decide to start paying out more/less at certain intervals. Maybe once a quarter. \$\endgroup\$
    – trichoplax
    Aug 15, 2014 at 17:15
  • \$\begingroup\$ So the bots are just buying and selling shares of each other, not any outside entity? What reason is there to choose one bot to invest in over another? Player decisions that someone's bot idea looks promising? \$\endgroup\$
    – xnor
    Aug 20, 2014 at 0:29
  • \$\begingroup\$ @xnor There are a few ideas to kick-start trading which have not been decided on yet, such as allowing the bots to announce the permille they will pay in dividends. \$\endgroup\$
    – PhiNotPi
    Aug 20, 2014 at 1:11
4
\$\begingroup\$

Brainfuck compression

Possible Duplicate

As it stands, this challenge could be labelled as a duplicate of others, as it is a base conversion. Please suggest ways of avoiding this in the comments. (Perhaps make interpreting the compressed code part of the challenge?)

Challenge

For many code golfers, Brainfuck is the language of choice. However, it is horrifyingly wasteful: it only uses eight symbols (.,<>+-[]) out of a character set of 256.

Your task is to convert it into a compressed format, as follows:

  1. Receive Brainfuck code on standard input or equivalent.
  2. Remove characters which are not .,<>+-[].
  3. Convert [ to 000, ] to 001, + to 010, - to 011, . to 100, , to 101, < to 110 and > to 111.
  4. Group the resulting string into bytes, e.g. ,[.,] becomes 10100010 01010011.
  5. If the last "byte" is fewer than 8 bits long, add ones until it is 8 bits long. (Note: these may get interpreted as > instructions when the code is run or decompressed, but since they are at the end of the program, it doesn't matter.)
  6. Output the bytes to standard output.

Note: If the input does not contain any Brainfuck characters, the output should be empty.

Todo

Could this challenge include decompression as well?

Would a separate challenge for decompression or directly interpreting the compressed code be a duplicate?

Possible bonuses: -50 for removing <>, ><, +-, -+ from the code (golfing)

\$\endgroup\$
24
  • 1
    \$\begingroup\$ Nice challenge! I think it would be appropriate to include decompression aswell personally. The NULL byte could be an issue, especially for C programmers, but as you said, as long as you don't use two consecutive [s, everything should be okay \$\endgroup\$ Jul 24, 2014 at 7:07
  • 2
    \$\begingroup\$ Also, you might add information about how non-brainfuck characters should be handled (e.g. if you provide abcd as input) \$\endgroup\$ Jul 24, 2014 at 7:10
  • \$\begingroup\$ @HackerCow I'm trying to keep it simple, so I'm not sure about the decompression or interpreting. As a pure code-golf, would you just ask for two programs? (could be separated into two questions) Alternatively, it could be a code-reuse challenge, where the compressor and the decompressor/intepreter have to be as similar as possible (score=program1length+program2length+levenshteindistance) \$\endgroup\$
    – user16402
    Jul 24, 2014 at 7:17
  • \$\begingroup\$ Well you could potentially ask this one now and post a "sequel" to it later, handling the decompression part. The code-reuse would also be a great idea, but that would definetely be a challenge ;) \$\endgroup\$ Jul 24, 2014 at 7:21
  • \$\begingroup\$ @HackerCow I'm worried that a separate decompression challenge might be a dupe of this one... \$\endgroup\$
    – user16402
    Jul 24, 2014 at 7:23
  • \$\begingroup\$ True, although I have seen sequels to questions before, so I don't think it would be a problem... Some mod might be able to help here \$\endgroup\$ Jul 24, 2014 at 7:24
  • 1
    \$\begingroup\$ @professorfish You could ask for two programs/functions, and take the sum of both lengths as score. \$\endgroup\$
    – ProgramFOX
    Jul 24, 2014 at 10:26
  • \$\begingroup\$ @ProgramFOX True, but if the two programs aren't really connected, maybe it is better to have two separate challenges - the only problem is that they might be considered dupes...??? \$\endgroup\$
    – user16402
    Jul 24, 2014 at 14:00
  • \$\begingroup\$ @professorfish Yes, they might be considered dupes, as a decompressing algorithm for this is probably the compression one reversed. But if you don't like having both in one challenge, you can also create a compression challenge without decompression. \$\endgroup\$
    – ProgramFOX
    Jul 24, 2014 at 14:37
  • \$\begingroup\$ This is just a base conversion with unusual digits, so it's essentially a duplicate of codegolf.stackexchange.com/q/4423/194 \$\endgroup\$ Jul 24, 2014 at 15:01
  • \$\begingroup\$ @PeterTaylor There is a base conversion involved, although it isn't the only thing there is. would having the user create two programs, a compressor and an interpreter of the compressed data, be better? \$\endgroup\$
    – user16402
    Jul 24, 2014 at 15:10
  • \$\begingroup\$ Ok, the compression also involves a filter, but that's a trivial pre-processing step before the base conversion task which has already been done. IMO base conversion is a trivial task per se, and since Interpret BF has been done I would regard an interpreter of the compressed data as also being a dupe. See also meta.codegolf.stackexchange.com/q/1571/194 \$\endgroup\$ Jul 24, 2014 at 15:15
  • \$\begingroup\$ @PeterTaylor OK. "Alternatively, it could be a code-reuse challenge, where the compressor and the decompressor/intepreter have to be as similar as possible (score=program1length+program2length+levenshteindistance)" - is that a dupe as well? \$\endgroup\$
    – user16402
    Jul 25, 2014 at 7:32
  • 1
    \$\begingroup\$ @Kroltan so the longer the decompressor the better? \$\endgroup\$
    – user16402
    Jul 26, 2014 at 6:42
  • 1
    \$\begingroup\$ I think this would be less likely to be considered a duplicate if the method of compression was not so strictly defined. For example, allowing the use of Huffman coding instead of fixed length 4 bit codes may allow better compression for programs of non-trivial length. You could allow people to come up with their own method of compression and including the compressed sizes of a list of test programs in their score. Alternatively you could base the score purely on the compressed size and not limit the size of the compression program. \$\endgroup\$
    – trichoplax
    Jul 28, 2014 at 22:15
1
5 6
7
8 9
131

You must log in to answer this question.

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