539
\$\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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

3549 Answers 3549

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

I'm Jelly of Python (Cops)

I'm Jelly of Python (Robbers)

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

Decode Polybus Square/Tap Code/Prison Code

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

Plz Halp I Need $$$ Again

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

Input Format

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

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

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

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

Output

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

Test Cases

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

Rules

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

Meta

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

posted

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

Drop some boxes

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

Ouput Input... Forever

Problem

Given input chars, output them repeatedly forever.

Examples

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

Dedication: This is for all the tarpits out there!

Questions

  • Should a delimiter be allowed?
  • I was imagining that the input would be cycled through infinitely in order, like in the examples. Should we enforce that as a rule, though?
    • Or should the rules just be: Each char of input should eventually occur infinitely many times in output. (Informally stated, but can easily be made mathematically precise.)
  • Other thoughts!
\$\endgroup\$
4
  • \$\begingroup\$ If you go with "Each char of input should eventually occur infinitely many times in output", then you'd need to specify that no other characters should be outputted because otherwise you could just output all bytes in order, or output random bytes infinitely \$\endgroup\$
    – pxeger
    Aug 6 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 at 13:49
  • \$\begingroup\$ Are you going to post this? :) \$\endgroup\$
    – emanresu A
    Aug 13 at 22:30
  • \$\begingroup\$ Are you going to post this? It's been a month.... \$\endgroup\$
    – emanresu A
    Sep 6 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 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 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 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 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 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 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 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 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 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 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 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 at 8:11
5
\$\begingroup\$

Convert prefix to infix

\$\endgroup\$
2
  • \$\begingroup\$ Dupe? \$\endgroup\$
    – Dingus
    Nov 18 at 23:09
  • \$\begingroup\$ @Dingus Yes, I'll just do prefix to infix instead :P \$\endgroup\$
    – emanresu A
    Nov 19 at 3:31
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 '11 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 '11 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 '11 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 '11 at 14:53
  • \$\begingroup\$ Thanks. I updated the text problem to include some books from Gutenberg. \$\endgroup\$
    – Alexandru
    Jun 22 '11 at 15:04
  • \$\begingroup\$ Related \$\endgroup\$
    – Beta Decay
    Sep 7 '16 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 '17 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 '17 at 15:20
  • \$\begingroup\$ @programmer5000 The OP hasn't been seen since 2011, I think you're fine. \$\endgroup\$ Jul 21 '17 at 13:21
4
\$\begingroup\$

Count Syllables

The goal of this challenge is to write a program that can count the syllables in a word as accurately as possible.

Input

On STDIN, your program will receive a number X followed by X lines, each containing a single word. Simple enough. (Should there be a limit on the size of X?) The words will come from this list.

4
challenge
to
count
syllables

Output

Your output should be to STDOUT and have X lines. On each line should be the number of syllables counted in that word.

2
1
1
3

Scoring

To score you program, it will receive a long secret list of words to test. All programs will receive the same list of words. For each word, the number of syllables that your program got wrong will be added to the score of the program. If it output a 4 or a 2 when the word had 3 syllables, then one point will be added. If it said a 15 instead of a 3, then 12 points will be added to the score. The lower the score, the better.

For example, if for the above input your program output 3 2 2 2 (which would be produced by a program that counts strings of vowels), then the program would receive a score of 2.

Rules

Your program should not access any external files (such as the word list). Also, your program should be no more than 5,000 bytes long (is this a reasonable limit?).

The winner will be the person whose program has the lowest score, therefor the most accurate syllable counter. The deadline for submissions is [some time at least a month away].

Suggestions

I am open to all constructive criticism. Is 5,000 bytes a reasonable limit for the program size? How long should the official scoring test be? How long should the deadline be?

\$\endgroup\$
10
  • 12
    \$\begingroup\$ This has one major flaw: the output is subjective. How many syllables do these words have? Every; victory; hierarchy; desire; oil; hour; poem. The only real way I see to work around this is for you to produce a marked-up version of the word list. \$\endgroup\$ May 29 '12 at 20:40
  • \$\begingroup\$ I was really worried about that, and I don't see a way around it. \$\endgroup\$
    – PhiNotPi
    May 29 '12 at 20:42
  • 1
    \$\begingroup\$ I personally would love to see more language processing challenges. I agree with @PeterTaylor on the difficulty of some words. Perhaps taking a specific text(s) and identifying explicitly in the challenge which words will have how many syllables? \$\endgroup\$
    – Gaffi
    Jun 8 '12 at 3:34
  • 2
    \$\begingroup\$ @PeterTaylor ...Or maybe you could filter ambiguous words out of the reference list? \$\endgroup\$
    – user16991
    Feb 8 '15 at 1:19
  • 1
    \$\begingroup\$ What's the point of the first line of input? \$\endgroup\$
    – msh210
    Apr 27 '16 at 20:05
  • 3
    \$\begingroup\$ If you provide a reference list, A hyphenated reference list, and hide a secret list which may or may not include members of the reference list, this would be a reasonable challenge \$\endgroup\$ Sep 17 '16 at 0:05
  • \$\begingroup\$ Do you plan to post this? If not, I'd be happy to adopt it. (If you don't respond within two weeks, by community standards, I'm allowed to do so.) \$\endgroup\$
    – MD XF
    Aug 18 '17 at 3:20
  • \$\begingroup\$ The example of inaccurate program that would score 2 - did you mean to output 3 1 1 2 rather than 3 2 2 2? \$\endgroup\$
    – Heimdall
    Nov 9 '17 at 18:31
  • \$\begingroup\$ A reference list could be dynamic: potential contestants can ask for words of their choice to be added to the list. They won't know what's on the secret list but will try to make their programs as accurate as possible (according to your syllable count) so they should always be able to ask for specific words they are not sure about. Of course, you could make it in different language. In my language, Slovene, it's much clearer how many syllables words have. How about Solresol, haha! \$\endgroup\$
    – Heimdall
    Nov 9 '17 at 18:38
  • \$\begingroup\$ I am going to adopt this if you don''t respond \$\endgroup\$ Dec 20 '17 at 16:48
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 '13 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 '13 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 '13 at 9:34
  • \$\begingroup\$ @PhiNotPi Thanks, question edited! \$\endgroup\$
    – F. Hauri
    Dec 14 '13 at 9:42
  • \$\begingroup\$ @PeterTaylor I've already browsed calendar questions ;-) \$\endgroup\$
    – F. Hauri
    Dec 14 '13 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 '13 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 '17 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 '13 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 '13 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 '13 at 14:10
  • \$\begingroup\$ @JanDvorak Okay, that's a fair point. \$\endgroup\$
    – Gareth
    Dec 23 '13 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 '13 at 14:15
  • \$\begingroup\$ Is the solid border guaranteed? \$\endgroup\$ Dec 23 '13 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 '13 at 16:43
  • \$\begingroup\$ Also, what if there are multiple paths? Which path should we choose? \$\endgroup\$ Dec 23 '13 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 '13 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 '13 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 '13 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 '13 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 '13 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 '13 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 '13 at 9:46
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 '14 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 '14 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 '14 at 0:58
  • \$\begingroup\$ That may be better. \$\endgroup\$ Apr 21 '14 at 21:08
  • \$\begingroup\$ Would you allow the usage of predefined functions that calculate the aliquot sum? \$\endgroup\$
    – Wrzlprmft
    Apr 22 '14 at 13:49
  • \$\begingroup\$ @alexander-brett Are you going to post this? \$\endgroup\$
    – Oliver Ni
    Oct 9 '16 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 '17 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 '14 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 '14 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 '14 at 2:44
  • 1
    \$\begingroup\$ @A.L what does T signify? \$\endgroup\$
    – trichoplax
    Jul 19 '14 at 21:21
  • \$\begingroup\$ @githubphagocyte oops, I wrote T for Top, it's U instead. \$\endgroup\$
    – A.L
    Jul 19 '14 at 23:06
  • 1
    \$\begingroup\$ @A.L so .RUUBFULRR? Makes sense now thank you. \$\endgroup\$
    – trichoplax
    Jul 19 '14 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 '17 at 16:53
  • \$\begingroup\$ @programmer5000 You're welcome :-) \$\endgroup\$
    – r3mainer
    Jun 10 '17 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 at 7:21
  • \$\begingroup\$ @HackerCow I'm worried that a separate decompression challenge might be a dupe of this one... \$\endgroup\$
    – user16402
    Jul 24 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 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 '14 at 7:32
  • 1
    \$\begingroup\$ @Kroltan so the longer the decompressor the better? \$\endgroup\$
    – user16402
    Jul 26 '14 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 '14 at 22:15
4
\$\begingroup\$

Comment Java Code

Little Billy is in an AP computer science class and his teacher requires him to comment his code (in Java) even though Little Billy thinks it is redundant. Little Billy is a lazy person and so he wants a program to comment for him.

The Challenge:

Make a program in any language that gets a text file as input and saves the commented version to a new text file (or to STDOUT) changing it in the following ways:

  • Add comments before all contructors:

/**
* Constructs a new instance of (class whatever).
* if applicable: @param nameOfVariable is the name of variable
*/

  • Add comments before any functions:

/**
* if applicable: @param nameOfVariable is the name of variable.
* if applicable: @return nameOfReturnVariable is the name of return variable.
*/

  • Add a comment before static void main(String[] args) if present:

/**
* This is where the program starts.
* @param args is the command line arguments passed to the program.
*/

  • Add comments before the class declaration (not applicable for inner classes)

/**
* class NameOfClass is another great example of Object Oriented Programming!
*/

For example, given this:

public class Car {
    private double gas;
    private double mpg;

    public static void main(String[] args) {
        new Car(20,20);
    }

    public Car(){}

    public Car(double gasInVehicle, double milesPerGallon){
        gas = gasInVehicle;
        mpg = milesPerGallon;
    }

    public void drive(double milesToDrive){
        gas-=(milesToDrive/mpg);
    }

    public double getGas(){
        double gasolineInTank = gas;
        return gasolineInTank;
    }

}

Your program should output this:

/**
 * class Car is another great example of Object Oriented Programming!
 */
public class Car {
    private double gas;
    private double mpg;
    /**
     * @param args is the command line arguments passed to the program.
     */
    public static void main(String[] args) {
        new Car(20,20);
    }
    /**
     * Constructs a new instance of Car.
     */
    public Car(){}
    /**
     * Constucts a new instance of Car.
     * @param gasInVehicle is the gas in vehicle.
     * @param milesPerGallon is the miles per gallon.
     */
    public Car(double gasInVehicle, double milesPerGallon){
        gas = gasInVehicle;
        mpg = milesPerGallon;
    }
    /**
     * @param milesToDrive is the miles to drive
     */
    public void drive(double milesToDrive){
        gas-=(milesToDrive/mpg);
    }
    /**
     * @return gasolineInTank is the gasoline in tank.
     */
    public double getGas(){
        double gasolineInTank = gas;
        return gasolineInTank;
    }
}

Extended Info

  • Because Little Billy's class is only on week 3, Little Billy's knowledge of complex Java statements is pretty limited. In other words, only common functions, class declarations, constructors and instance variables will be included; objects/variables/resources are limited to Java primitives and their wrapper classes and Math.
  • Each variable name is separated for its definition according to standard camel case rules, with an exception of the first letter, which may be capitalized. For example,

milesToRun = miles to run.
milestoRun = milesto run.
MilesToRun = miles to run.
parseXML = parse xml - each successive capital letter (with a minimum of 3 in a row) is considered an acronym, so GetABuffer would become get a buffer. parseXM is parse x m.

If it is a parameter -

@param milesToRun is the miles to run.

  • Your program should be able to handle multiple arguments to functions
  • There should be no lines with only " * ".
  • Assume all variables and parameters are formatted correctly (e.g. all camel case, only letters, etc.)
  • Indentation is not critical. However, all newlines should remain.
  • You may also assume that statements ending in a semicolon are 1 line each

Scoring

This is code-golf, so shortest code wins (in bytes).

\$\endgroup\$
3
  • 1
    \$\begingroup\$ when you say "assume all camel case"... what about the unlikely method name GetABuffer? If that is valid and should produce "get a buffer", then what about ParseXML? \$\endgroup\$ Sep 11 '14 at 10:12
  • 1
    \$\begingroup\$ Similar to codegolf.stackexchange.com/q/3241/194 . The thing that would potentially make this more difficult is parsing Java, but then you need to provide some details on the grammar. I also notice that your spec and examples avoid all of the tricky stuff around generics. \$\endgroup\$ Sep 11 '14 at 11:32
  • \$\begingroup\$ I think it should be parseXml. \$\endgroup\$ Sep 13 '14 at 15:07
4
\$\begingroup\$

Coloring Book

Given a black-and-white raster line drawing (no anti-aliasing, with fully enclosed regions), write a program that will color it in. Something maybe like below, though I'd clean up messy JPGs into clean B&W PNGs to start with:

http://wallalay.com/wp-content/uploads/2014/07/Coloring-Books-27.jpg

Could either be a , to give freedom in create more interesting output (gradients, patterns, how to select "better" colors, other images). Along the lines of patterns and gradients, I'd opt for simpler stock "prompts", preferably animals, to show off solutions:

http://www.frontiernet.net/~goofis1/Images/Dinosaurs/SlateBack.jpg

...or perhaps if each region has a specified color given by a swatch inside it: so the program would basically need to find-the-color then flood-fill. Sounds boring, I prefer more creativity.

\$\endgroup\$
6
  • \$\begingroup\$ The flood fill would indeed be quite trivial, but as a popularity contest this could become too much of an art contest and less of a programming contest. \$\endgroup\$ Oct 10 '14 at 9:45
  • \$\begingroup\$ In my mind's eye I kinda pictured an elementary school classroom wall with the same line drawing jazzed up every which way. \$\endgroup\$
    – Nick T
    Oct 10 '14 at 10:18
  • \$\begingroup\$ I do think there is reasonable technical skill involved in creating something to dynamically create said art. Gradients, patterns, masking other images into regions, coloring outside the lines, and something even more interesting than what I can come up with all seem to take reasonable skill. Especially for a few arbitrary input drawings. \$\endgroup\$
    – Nick T
    Oct 10 '14 at 10:26
  • 2
    \$\begingroup\$ If you can come up with a testable criterion, you might be able to get an interesting code-golf which asks for cel shading rather than just floodfill. \$\endgroup\$ Oct 10 '14 at 10:42
  • \$\begingroup\$ You could specify a rule for which colour should be used. For example, you could colour based on area or perimeter of the region being filled (or some combination of both). This would colour similar regions in similar colours and give the impression of being chosen for the image, but would still be rigorously defined enough to make it a code golf. \$\endgroup\$
    – trichoplax
    Aug 26 '15 at 14:50
  • \$\begingroup\$ @programmer5000 feel free to take this one. Are you thinking about doing code-golf somehow or a popularity contest? \$\endgroup\$
    – Nick T
    Jun 9 '17 at 23:09
4
\$\begingroup\$

Score a Mahjong Hand

So you've built a solver for which tiles you need to complete a Mahjong hand, but you've heard that certain hands are worth more than others and sometimes a hand that scores too low can't even win.

So, you decide to build a program that will score hands for you.

This time, however, you will be making it for the full mahjong set. There are a total of 136 tiles in this variant, four copies of each of the following:

  • 1 coin to 9 coins, represented from 1p to 9p.
  • 1 stalk to 9 stalks, represented from 1s to 9s.
  • 1 myriad to 9 myriads, represented from 1m to 9m.
  • four winds, represented as EE, SS, WW, and NN.
  • three dragon tiles, represented as ZZ, FF, and BB.

The winds and dragons are known as honour tiles, and they are not part of any suit.

A standard mahjong hand consists of four sets and a pair. A set can be any of:

  • A chow, which is a sequence of three tiles in the same suit. Winds and dragon tiles cannot be part of a chow.
  • A pong, which is a group of three of the same tile.
  • A kong, which is a group of four of the same tile. Every kong increases the total number of tiles in a player's hand by 1.

Every chow and pong has three tiles in it, while a kong has four. So a winning hand can have anywhere from 14 to 18 tiles, depending on the number of kongs.

Now, the score that a hand has is based on fan. A valid winning hand has no fan by default. However, the following patterns count for fan:

Sets

  • A pong or kong of dragons (e.g. ZZ ZZ ZZ): 1 fan
  • A pong or kong of winds (e.g. EE EE EE or SS SS SS SS): 1 fan

Patterns

  • A straight, 1-9 in a suit as three sets (e.g. 1s 2s 3s 4s 5s 6s 7s 8s 9s + 1 more set and a pair): 3 fan
  • A broken straight, 1-9 in a suit plus an additional 3, 5, and 7 (1s 2s 3s 3s 4s 5s 5s 6s 7s 7s 8s 9s): 5 fan
  • A pong or kong of all three dragons (e.g. ZZ ZZ ZZ FF FF FF BB BB BB BB): 7 fan
  • Four winds (EE EE EE SS SS SS WW WW WW NN NN NN + a pair): 10 fan
  • Nine Gates (1 1 1 2 3 4 5 6 7 8 9 9 9 of any single suit, plus one more of any tile in the suit): 14 fan (effectively 20 fan because of one-suit)

Entire hand patterns

  • Entire hand is chows (e.g. 1s 2s 3s 6s 7s 8s 2p 3p 4p 7m 8m 9m NN NN): 1 fan
  • Entire hand is pongs or kongs (but not all kongs) (e.g. 1m 1m 1m 3s 3s 3s 7p 7p 7p NN NN NN EE EE): 3 fan
  • Entire hand is kongs only (e.g. 1m 1m 1m 1m 3s 3s 3s 3s 7p 7p 7p 7p NN NN NN NN EE EE): 10 fan
  • All tiles from one suit + honours (e.g 1p 1p 1p 4p 4p 4p 7p 8p 9p SS SS SS EE EE): 3 fan
  • All tiles from one suit (e.g. 1p 1p 1p 4p 4p 4p 7p 8p 9p 6p 6p 6p 5p 5p): 6 fan
  • All tiles honours (e.g NN NN NN ZZ ZZ ZZ BB BB BB SS SS SS EE EE): 9 fan

Special hands

The hands below are scored specially and do not follow the four-sets-and-a-pair rule.

  • Seven Pairs (seven pairs of any tiles): 2 fan
  • Seven pairs in the same suit: 10 fan
  • Seven honour pairs: 20 fan
  • Thirteen Orphans (1p 9p 1s 9s 1m 9m EE SS WW NN ZZ FF BB and one more of any of these 13): 10 fan

Note that you only have to account for the value of the hand itself - you don't need to care about what the prevailing wind is or whether the tile was self-drawn, by discard, or anything else.

Also note that a hand may fulfill multiple criteria. If it does, add up all the fan from each criterion it fulfills, except if the hand is a special hand.

\$\endgroup\$
9
  • \$\begingroup\$ I won't be around for long. But sure, if you can make a chatroom and link to it here, I'll check in on it periodically. \$\endgroup\$
    – Joe Z.
    Dec 19 '14 at 3:40
  • \$\begingroup\$ Chat link: here \$\endgroup\$
    – Sp3000
    Dec 19 '14 at 3:47
  • \$\begingroup\$ Oh, just using that one? It might get muddled up in the rest of the messages, though. \$\endgroup\$
    – Joe Z.
    Dec 19 '14 at 5:25
  • \$\begingroup\$ Some ambiguous case that never happens in a real game: 111122233345555, which can be either 1111 222 33 345 555 or 11 123 123 234 5555. Both are 6 fan, though. Btw: psm are Japanese and ZFB are Chinese. Shouldn't that be at least consistent? (Or is that the standard somewhere?) \$\endgroup\$
    – jimmy23013
    Dec 19 '14 at 11:01
  • \$\begingroup\$ @user23013 In my question I was using Japanese, just so I could plug tests into Tenhou's solver. They use 1z2z3z... for honours. ZFB is indeed Chinese, but unfortunately taking the initials for Japanese gives CHH. I'm not sure if there's a standard anywhere. \$\endgroup\$
    – Sp3000
    Dec 19 '14 at 14:21
  • \$\begingroup\$ @Sp3000 In fact it would be HHC in the Japanese order... I think most Japanese people don't use letters for honors. And Chinese people don't use letters at all. I did some search and found some English-speaking people are just using something worse: Red, Green, ... \$\endgroup\$
    – jimmy23013
    Dec 19 '14 at 15:48
  • \$\begingroup\$ ZFB is Chinese, and psm was Japanese/Cantonese but there I was just following the convention from the previous question. I can change it to BSW if you want, though. \$\endgroup\$
    – Joe Z.
    Dec 19 '14 at 20:30
  • \$\begingroup\$ I was just nitpicking... never mind. \$\endgroup\$
    – jimmy23013
    Dec 20 '14 at 9:56
  • \$\begingroup\$ The multiple maching criteria should be clarified: For example seven pairs in the same suit, scores just 10 total - not 12. In otherwords, it isn't considered to match both "Seven Pairs" and "Seven Pairs in the same suit". \$\endgroup\$ Jan 2 '15 at 15:42
4
\$\begingroup\$

Invert the matrix

The name says it all. I am surprised that there is no preexisting question on calculating matrix inversion

Given an nXn invertible matrix, your task is to output its inverse.

Rules

  • Floating point precision of at least 3 significant decimal places is required
  • You can assume that the input matrix will always have an inverse
  • You cannot use any inbuilt methods (or external libraries) to perform any of the following tasks:
    • Calculate the inverse
    • Solve system of equations
    • Calculate determinant
    • Multiply two matrices or calculate dot product.
  • In other words, your code has to calculate the inverse using any of the mathematical methods itself. (If I missed out any inbuilt methods in the above rule, this rule should make it clear that it cannot be used)
  • You cannot calculate inverse by randomly generate random matrix and then multiply with the input to check for unit matrix.

Input

Input can be in a format of your choice. For example:

[[ 1, 3, 4],
 [ 5, 7, 8],
 [ 3, 4, 5]]

or

1 3 4
5 7 8
3 4 5

etc

Output

The output should be in the same format as the input, except for 1 requirement that each row of the matrix should be in a separate line with elements of the same row on the same line.

This is code-golf so shortest code in bytes win.

Sandbox notes

What do you think of the problem ? Too mundane ? Too trivial ? Need any extra rule to make it more interesting ?

\$\endgroup\$
13
  • \$\begingroup\$ There is a pre-existing question, although it only covers 2x2. \$\endgroup\$ Jan 3 '15 at 8:28
  • \$\begingroup\$ @PeterTaylor Yeah, also, it is based on system of equations, which is related but not exactly same as Inverse (Inverse is a part of solving equations). So size plus this fact should make this question different enough ? \$\endgroup\$
    – Optimizer
    Jan 3 '15 at 8:32
  • \$\begingroup\$ "Floating point precision upto 3 decimal places is required" - did you mean "Floating point precision of at least 3 decimal places is required"? \$\endgroup\$ Jan 3 '15 at 10:11
  • \$\begingroup\$ @JanDvorak err. \$\endgroup\$
    – Optimizer
    Jan 3 '15 at 10:13
  • 4
    \$\begingroup\$ The whole business of numerical accuracy is a minefield for this because there are many ill-conditioned instances. You can't talk in terms of decimal places unless you either require people to work in arbitrary precision or guarantee some very conservative bounds on the input and output values. (Unless you want to merely go for conservative bounds and include some test cases which will disqualify naïve Gaussian elimination and force people to do a Bareiss-style approach, but that will lead to having not more than one or two correct answers and probably a dozen incorrect ones). \$\endgroup\$ Jan 3 '15 at 16:34
  • \$\begingroup\$ To get around thorny questions of ill-conditioned matrices and the possibility of divide-by-zero, how about only requiring that the algorithm work with high probability on random Gaussian matrices of size at most 100? \$\endgroup\$
    – xnor
    Jan 3 '15 at 18:00
  • \$\begingroup\$ @PeterTaylor I might not have understood even 10% of that comment. Can you please tell me what can I put in place of that rule then ? \$\endgroup\$
    – Optimizer
    Jan 3 '15 at 19:14
  • \$\begingroup\$ @xnor what do you mean by ill-conditioned matrices ? \$\endgroup\$
    – Optimizer
    Jan 3 '15 at 19:15
  • \$\begingroup\$ No, I can't. I don't consider myself qualified to write a spec for inverting matrices. I know what the problem is, but I don't understand it well enough to formulate validity constraints. I think it would be best to leave the idea for someone who has a firm grasp of the numerical analysis of linear algebra to pick up and finish. \$\endgroup\$ Jan 3 '15 at 19:41
  • \$\begingroup\$ @PeterTaylor I disagree with you. The purpose of this challenge is not to get an mathematically perfect matrix inversion code, but instead, a code that calculates the inverse in the shortest and smartest way. Martin suggested in chat that the floating point precision upto certain significant digits can be made a compulsion till a matrix size of say 10. Simply hoping to get a mathematically experienced person who has mastery in matrix inversion to pick up the challenge is a very pessimistic approach. \$\endgroup\$
    – Optimizer
    Jan 3 '15 at 20:38
  • \$\begingroup\$ @Optimizer Here's the issue: say I write a row reduction algorithm. I want to subtract a multiple of the first row from the second in order to zero out the first entry of the second row. Do I have to consider the case where the first entry of the first row is zero, so I get a divide-by-zero error? Ok, say I have a separate check if equals 0. What if that entry is supposed to be 0, but as a result of a previous calculation is 0.00000001, failing the check? Now my second row is ginormous and it shouldn't be. \$\endgroup\$
    – xnor
    Jan 4 '15 at 2:47
  • \$\begingroup\$ @Optimizer Alternatively, finding the inverse mod 2 would avoid accuracy issues. \$\endgroup\$
    – xnor
    Jan 7 '15 at 4:21
  • \$\begingroup\$ @xnor mod 2 as in ? \$\endgroup\$
    – Optimizer
    Jan 7 '15 at 4:27
4
\$\begingroup\$

Responsible governance

Background

For years, the Federal government of the United States has been in chaos. The Presidency and Congress are under different parties, and there are no compromises in sight. Instead of passing a budget or improving the tax code, the politicians are squabbling as the country teeters on the brink of economic collapse. It seems that a few more years of political dysfunction will soon reduce the United States to rubble.

Yet, some have noticed that many state governments seem to be functioning. Taxes are being reformed, education is being improved, and even compromise can be found on occasion!

The solution is clear. The federal government must be dissolved. Each state will control its own eduction, infrastructure, and healthcare, but the budgets will be pooled. As the governor of your state, you must use the country's funds to improve your constituents' lives, but also be frugal enough to let your neighbors prosper as well.

Rules

This system of government will be in place for 10 years (120 months), after which the results of this experiment will be analyzed. Each month, every governor will be given the opportunity to use the country's funds to pay for one project of their choice.

The government starts with $1,000,000 in the bank, times the number of states. In every state, life expectancy is 75 years, education is at 95 IQ, and the infrastructure gets a rating of 65 points.

Every year, the following happens:

  • First, taxes are collected and centralized expenses are paid.
  • For each of the next twelve months:
    • Each governor, in order, is allowed to finance a project.
  • Finally, information about each states' education, healthcare, and infrastructure is updated to reflect the projects built.

Scoring

The final score is the government's total funds, times average state's life expectancy, times the average state's IQ, times the average state's infrastructure rating. (These averages are not weighted by population.)

This entire experiment will be performed many times. Each time, a different governor will be excluded. The winner will be the governor such that the final score is the worst when they are excluded, since they must have had the biggest impact on the government's success.

Details

  • N is the number of governors (not counting the excluded one)
  • L is the life expectancy of a particular state.
  • La is the average life expectancy.
  • E is the IQ of a particular state.
  • Ea is the average IQ.
  • T is the infrastructure rating of a particular state.
  • Ta is the average infrastructure rating.

    Revenues and expenses

  • Annual revenue: $ N Ea2 Ta

  • Annual expenses: $10,000,000,000,000 N / La3 / Ta

    Projects

  • Each of the three factors (health, education, and infrastructure) is calculated on a state-by-state basis. L starts at 75, E starts at 95, and T starts at 65.

  • For each factor, the bonuses are cumulative.
  • For example, the bonuses L +2, L +5 mean that L = ( 75 + 2 + 5 ) = 82.
  • Each project can be done only once by each state.
  • Each project has an associated six-letter code (for I/O).

    List of projects

  • [ENOUGH] Enough medicine: L +5, cost: $300,000

  • [CANSCR] Early cancer screenings: L + 4, cost $200,000
  • [FREECC] Free community college: E +10, cost: $400,000
  • [LIBRAR] Library system: E + 3, cost: $150,000
  • [MUSEUM] Museums E + 1 in each state, cost: $500,000

many more in the actual challenge...

Your program

Write a function in Java, Python 2, or Ruby, which accepts an integer (the government's funds) and returns an optional six-letter code, corresponding to the project chosen. If nothing is returned, or the returned value is invalid, or the chosen project was already built by you, or costs more than the government's funds, no project will be built for this month.

You may not use any I/O, except for one file called "<program-name>.txt, which you may use however you wish, provided it's kept under 2 megabytes at all times.


Some questions:

  1. Are the rules completely clear?
  2. Are there any perverse incentives? The goal should be to improve one's own state while being frugal with the government's funds.
  3. In the first section too political?
  4. Is the challenge too complicated?
\$\endgroup\$
2
  • \$\begingroup\$ I wonder about the formulas used for score/revenue/expenses. Have you run this a few times with dummy states to see if it works in practice? I'd hate to see a simple, constant choice resulting in a clear winner with no good way to stop it. \$\endgroup\$
    – Geobits
    Jan 26 '15 at 2:23
  • \$\begingroup\$ That's a good point; thanks for the feedback. The existing formulas are sort of placeholders for now. Once the other details are worked out, then I'll focus on getting the formulas balanced. \$\endgroup\$
    – Ypnypn
    Jan 26 '15 at 2:48
4
\$\begingroup\$

Real-Time Hovercraft Battle

Hovercrafts are cool. Hovercrafts with rail guns are even cooler. In this challenge, you will write a program to controller a battling hovercraft.

The hovercrafts in this game obey the laws of physics. A hovercraft with no acceleration will continue moving in a straight line. Also, a spinning hovercraft will continue to spin.

At each moment in time, the hovercraft's motion is defined by a few variables: the location, angle, linear velocity, and angular velocity of the hovercraft.

Hovercrafts are circles of radius 4, with a clear "front" and "back" end. On the left and right there are two forward-facing fans which serve as propulsion. Each fan has 8 power settings, from -3 to +4. These fans control additional aspects of the hovercraft's motion, the linear and angular acceleration.

Todo: determine the mass and moment of inertia for the hovercraft, which will then allow me to determine which power settings have which effects.

The real fun begins with the rail gun. The rail gun fires from the front of the hovercraft and deals damage when it strikes the side of the opposing hovercraft. The ammunition travels at a fast speed but finite, and the angle of the shot depends on the motion of the hovercraft. Firing the railgun also produces a recoil effect.

Note: I need to prevent the "rotating turret" strategy: spin really fast and fire when you find yourself pointed at something. An a truly instantaneous shot would never miss in this circumstance.

In order to power the rail gun, you must first charge a capacitor. Capacitor charging can be turned on and off. When the capacitor is charging, the fans will have reduced thrust. Once the capacitor stops charging (either it is full or charging is turned off) the thrusters will act normally again. You can still fire the rail gun when the capacitor is charging: the shot will have reduced damage. By default, the capacitor starts empty with charging on.

The Tournament

All of the participants will participate in a series of 1v1v1v1 battles. The goal is to survive the longest.

The battle arena is a radius 400 circle. Hovercraft can collide with the boundary, bounce,and take a little damage. At the start of the match, one hovercraft will be randomly located (1 per quadrant).

The finish order for a round will be determined by the order of death. After a certain period of time, all remaining hovercrafts will be deemed co-champions of that round.

After a decent number of battles (a number not currently determined, but something less than an exhaustive search but enough to determine the overall winner with non-negative confidence), the finish orders for each battle will be treated as ballots in a form of ranked voting scheme. By using a mathematically sound voting scheme, the final order should represent the results of the battles pretty well.

I have not started the controller yet.

This will be a real-time game. Each hovercraft program can request updates and send commands in real-time. This means that game ticks can happen while your program is running, and each game tick is a very small increment of time (as fast as feasible).

\$\endgroup\$
1
  • \$\begingroup\$ Check out Robocode. It is a long-running contest with comparable rules. What vision do the players have? Can you see the orientation of other participants? \$\endgroup\$
    – Franky
    Feb 15 '15 at 10:49
4
\$\begingroup\$

Best Approximating Polynomial

(?)

Let f(x) and g(x) be two continuous real-valued functions over the interval [a, b], where a < b.  The mean squared error (or simply "error" hereafter) between f(x) and g(x) is defined as

Equation 1

Roughly speaking, the smaller the error is, the closer f(x) and g(x) are.

In this challenge, f(x) will be some user-supplied target function and g(x) will be a polynomial of some maximal degree n.  The goal is to find the polynomial g(x) that minimizes the error w.r.t. f(x) (such a polynomial exists and is unique;) we say that g(x) is the best approximation of f(x) over the interval [a, b] using a polynomial of degree at most n.

For example, let's take the function f(x) = cos x over the interval [0, ½π] (which contains all the "interesting" information about this function), and look for a polynomial of degree at most 2. As you might know, the Taylor expansion of cos x up to degree 2 is t(x) = 1 - ½x2.  The error between t(x) and f(x) is approximately 6.25×10-3.  We can do better than that! If I got my math right, the best approximation of cos x over the interval [0, ½π] using a polynomial of degree at most 2 is (brace yourselves):

Equation 2

or approximately g(x) ≈ -0.34 x2 - 0.13 x + 1.02.  The error between g(x) and f(x) is approximately 7.03×10-5—two orders of magnitude better! The difference is very notable, as the following plot shows:

Plot 1

Challenge

Write a program or a function that takes a function f(x), an interval [a, b], where a < b, and a nonnegative integer n, and returns the polynomial of degree at most n that best approximates f(x) over the given interval.

Input

You may read the input through STDIN, the command line, as function arguments or an equivalent method. Note that you don't have to accept a, b and n in any specific format; particularly, you don't have to read a and b as [a, b].

You should accept the function f(x) in one of the following forms:

  • As a language-level function, function-like object, polymorphic object or any other equivalent method your language uses to communicate functions.
  • As a string containing an expression. The actual format of the string is flexible, but it should be expressive enough to allow basic arithmetic operations, exponentiation, and preferably also logarithms and basic trigonometric functions. The intention is for it to be used with something like eval. Note that you're allowed to require the string to be formatted in some convenient way (within reason), for example, pre-wrapped in a function
    (as in "function (x) { return x + Math.sin(x); }").
  • If, and only if, both of the above methods are impractical in your language, you may not take the function as input and assume that the function is already defined by the user. In this case, add to your score a +16byte penalty.

You may assume that the input is valid.

Please specify how your program accepts its input in your post.

Output

You may write the output to STDOUT, return it as the function's result or use an equivalent method. You may express the polynomial as a list of coefficients (e.g., [1, -2, 1]), using some pretty-printed form (e.g., x^2 - 2x + 1) or some other equivalent method. Either way, it should be easy to determine the coefficients of the different terms from your output; so, for example, you may not return the polynomial as an opaque function.

Note that unlike the example given at the beginning of the post, you don't have to produce symbolic output (unless you want to); a numeric output is fine.

Please specify how your program returns its output in your post. If the order of the coefficients may be ambiguous, make sure to clarify it.

Accuracy and Run Time

The numerical accuracy of your program is most likely going to be dependent on the target function, the degree of the polynomial and the amount of time you allow it to run. As a result, giving a general accuracy requirement is impractical. However, your program should process each of the below test cases in less than a minute and produce a polynomial whose error w.r.t. the target function is no worse than the error specified in the test case.

Additional Rules

  • You may not use any function that performs this specific task.

Scoring

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

Test Cases

Recall that your program should complete each of the following test cases in less than a minute, with an error that is less than or equal to the specified error. That being said, this is not a hard and fast rule; if your program struggles with a couple of test cases, that's fine. Note that the approximating polynomials listed in the test cases are just an approximation and are only given for illustration. Although theoretically each case has a unique optimal polynomial, your program might produce a notably different one; this is especially true for the higher degree polynomials. However, both polynomials should behave similarly over the given interval, which is why the correctness of your program is determined by the error. Likewise, the errors listed in the test cases are only an approximation and are not necessarily the errors of the corresponding listed polynomials—they're just a lower-bound for accuracy.

Test 1
f(x) = sin(x)
From: -pi
To: pi
Max. Deg.: 0
g(x) = 0
e^2 = 5.0001 * 10^-1

Test 2
f(x) = sin(x)
From: -pi
To: pi
Max. Deg.: 1
g(x) = 0.304 x
e^2 = 1.9604 * 10^-1

Test 3
f(x) = cos(x)
From: -pi
To: pi
Max. Deg.: 2
g(x) = -0.231 x^2 + 0.76
e^2 = 3.8032 * 10^-2

Test 4
f(x) = sin(x)
From: -pi
To: pi
Max. Deg.: 5
g(x) = 0.005643 x^5 - 0.155 x^3 + 0.988 x
e^2 = 1.8490 * 10^-5

Test 5
f(x) = cos(x)
From: 0
To: 3pi
Max. Deg.: 8
g(x) = 6.69465*10^-9 x^8 - 1.01005*10^-4 x^7 + 0.00332742 x^6 - 0.0400508 x^5 + 0.205029 x^4 - 0.351657 x^3 - 0.120773 x^2 - 0.169562 x + 1.01830
e^2 = 1.9764 * 10^-5

Test 6
f(x) = e^(-x^2)
From: -2
To: 2
Max. Deg.: 10
g(x) = -0.00143879 x^10 + 0.0211686 x^8 - 0.133468 x^6 + 0.473915 x^4 - 0.992265 x^2 + 0.999624
e^2 = 8.4405 * 10^-8

Test 7
f(x) = 1/(x^2 + 1)
From: -3
To: 3
Max. Deg.: 16
g(x) = 3.16504*10^-6 x^16 - 1.23974*10^-4 x^14 + 0.00203230 x^12 - 0.0181511 x^10 + 0.0966544 x^8 - 0.318123 x^6 + 0.662508 x^4 - 0.923653 x^2 + 0.996846
e^2 = 2.6 * 10^-6

Test 8
f(x) = e^((sin(x))^3)
From: 0
To: 2pi
Max. Deg.: 1
g(x) = -0.224 x + 1.87
e^2 = 2.6845 * 10^-1

Test 9
f(x) = (cos(x))^5
From: pi
To: 2pi
Max. Deg.: 17
g(x) = 6.31854*10^-12 x^17 - 1.63320*10^-11 x^16 - 2.78192*10^-10 x^15 - 8.73964*10^-10 x^14 - 2.74564*10^-9 x^13 + 5.59537*10^-8 x^12 - 2.70984*10^-8 x^11 - 2.61779*10^-5 x^10 - 2.67450*10^-7 x^9 - 8.40220*10^-7 x^8 + 0.3247516 x^7 - 7.3046333 x^6 + 72.908485 x^5 - 408.43197 x^4 + 1362.34294 x^3 - 2657.0269 x^2 + 2737.319113682029 x - 1100.1514
e^2 = 5.8 * 10^-5

Test 10
f(x) = sqrt(1 - x^2)
From: -1
To: 1
Max. Deg.: 20
g(x) = -627.601 x^20 + 2853.92 x^18 - 5499.47 x^16 + 5845.71 x^14 - 3738.80 x^12 + 1472.42 x^10 - 350.970 x^8 + 47.6426 x^6 - 3.39128 x^4 - 0.414096 x^2 + 0.999632
e^2 = 1.2 * 10^-6

Test 11
f(x) = sqrt(1 - x^2) + 0.1*sin(4*pi*x)
From: -1
To: 1
Max. Deg.: 18
g(x) = -203.563 x^18 + 141.013 x^17 + 821.952 x^16 - 757.063 x^15 - 1378.59 x^14 + 1771.07 x^13 + 1241.44 x^12 - 2345.58 x^11 - 648.127 x^10 + 1895.10 x^9 + 197.425 x^8 - 928.025 x^7 - 33.5970 x^6 + 254.982 x^5 + 2.70132 x^4 - 32.7510 x^3 - 0.590680 x^2 + 1.25167 x + 1.00047
e^2 = 1.9 * 10^-6

Test 12
f(x) = abs(x)
From: -1
To: 1
Max. Deg.: 6
g(x) = 1.46667 x^6 - 2.82024 x^4 + 2.30724 x^2 + 0.0854450
e^2 = 5.08635 * 10^-4

Test 13
f(x) = x*sin(x^1.2) + 10*sqrt(x)
From: 0
To: 2.5pi
Max. Deg.: 3
g(x) = -0.129 x^3 + 1.046 x^2 + 1.392 x + 6.98
e^2 = 7.3389 * 10^0

Test 14
f(x) = sin(log(1 + e^cos(x)))
From: 2
To: 10
Max. Deg.: 10
g(x) = 9.52190*10^-10 x^10 - 6.30342*10^-6 x^9 + 3.3746525*10^-4 x^8 - 0.0078575036 x^7 + 0.103708803 x^6 - 0.84926923 x^5 + 4.4421097 x^4 - 14.766225 x^3 + 30.153933 x^2 - 34.72483 x + 17.8389
e^2 = 5.4 * 10^-5

Test 15
f(x) = abs(log(x))
From: 1/e
To: e
Max. Deg.: 15
g(x) = 6.07034*10^-8 x^15 + 9.85444*10^-5 x^14 + 3.35349*10^-7 x^13 + 7.88206*10^-7 x^12 + 1.85260*10^-6 x^11 + 4.35436*10^-6 x^10 - 3.4245574 x^9 + 42.093925 x^8 - 228.714688 x^7 + 711.8547 x^6 - 1383.06 x^5 + 1720.8859 x^4 - 1357.596 x^3 + 651.1596 x^2 - 173.8175 x + 20.680
e^2 = 1.587 * 10^-4

Test Program

The following snippet can be used to compute the best approximating polynomial for a given function, as well as to calculate the error of your own approximations. Note that it has limited accuracy, and becomes numerically unstable for polynomials of degree over 20–30.

<style>#main {display: none;}#status_container {padding: 4px;}#status {padding: 5px;background-color: #fffdce;box-shadow: 1.5px 1.5px 3.5px #aaaaaa;font-size: 10pt;word-wrap: break-word;display: none;}#status[loading] {display: inline;}</style><span id="main"><table id="main_table"><tr><td><div id="plot_area"><div id="plot_float"><div id="plot_container"><div id="plot"></div></div></div></div></td><td><table class="field_table" id="field_table"><tr><td class="field_name">𝑓(𝑥)&nbsp;=</td><td><table class="padding_table"><tr><td><div class="input_container"><div class="input_underlay" id="expression0_underlay"></div><div class="input_error_underlay" id="expression0_error_underlay"></div><textarea class="input" id="expression0" spellcheck="false" oninput="update(0)">e^-(x/6) cos x</textarea></div></td></tr></table></td></tr><tr><td colspan="2"><table class="horz_field_table"><tr><td><table class="field_table"><tr><td class="field_name small_field_name">From</td><td><table><tr><td><div class="input_container"><div class="input_underlay" id="from_underlay"></div><div class="input_error_underlay" id="from_error_underlay"></div><textarea class="input" id="from" spellcheck="false" oninput="update()">0</textarea></div></td></tr></table></td></tr></table></td><td><table class="field_table"><tr><td class="field_name small_field_name">To</td><td><table><tr><td><div class="input_container"><div class="input_underlay" id="to_underlay"></div><div class="input_error_underlay" id="to_error_underlay"></div><textarea class="input" id="to" spellcheck="false" oninput="update()">2.5pi</textarea></div></td></tr></table></td></tr></table></td><td><table class="field_table"><tr><td class="field_name small_field_name">Max.&nbsp;Deg.</td><td><table><tr><td><div class="input_container"><div class="input_underlay" id="max_deg_underlay"></div><div class="input_error_underlay" id="max_deg_error_underlay"></div><textarea class="input" id="max_deg" spellcheck="false" oninput="max_deg_add(0)" onkeydown="return spinner_keydown(event, 'max_deg', max_deg_add)">3</textarea></div></td></tr></table></td><td><div class="button_group small_button_group"><table><tr><td><button class="increment pos_button fixed_button" id="max_deg_inc" title="Increment" onclick="max_deg_add(+1)">▲</button></td></tr><tr><td><button class="decrement neg_button fixed_button" id="max_deg_dec" title="Decrement" onclick="max_deg_add(-1)">▼</button></td></tr></table></div></td></tr></table></td><td class="separator"></td><td><div class="button_group"><button class="check_button" id="hold" title="Supress update" onclick="hold()">Hold</button></div></td></tr></table></td></tr><tr class="separated_row" id="expression0_0"><td class="field_name">𝑔(𝑥)&nbsp;=</td><td><table class="padding_table"><tr><td><div class="output_container"><div class="output polynomial" id="poly"></div></div></td></tr></table></td></tr><tr id="expression0_1"><td class="field_name"><span class="variable">ϵ</span><sup>2</sup>&nbsp;=</td><td><table class="horz_field_table"><tr><td><div class="output_container"><div class="output" id="poly_error"><table class="horz_field_table"><tr><td class="error_value" id="poly_error_value"></td><td class="error_change" id="poly_error_change"></td></tr></table></div></div></td><td><div class="button_group"><button class="add_expr pos_button fixed_button" id="add_expr0" title="Add function" onclick="add_expr(0, event.ctrlKey + 2 * event.shiftKey)">+</button><button class="remove_expr neg_button fixed_button" style="display: none;" id="remove_expr0" title="Remove function" onclick="remove_expr(0, event.ctrlKey)" disabled>-</button></div></td></tr></table></td></tr><tr class="options separated_row" id="flag_row"><td colspan="2"><table class="horz_flag_table"><tr><td><label class="flag_container" title="Plot legend"><table><tr><td><input type="checkbox" class="flag" id="legend" onchange="update(null, true)" checked></td><td>Key</td></tr></table></label></td><td><label class="flag_container" title="Extra accuracy"><table><tr><td><input type="checkbox" class="flag" id="extra_accuracy" onchange="update(undefined, true)"></td><td>Acc.</td></tr></table></label></td><td><label class="flag_container" title="Scientific notation"><table><tr><td><input type="checkbox" class="flag" id="scientific_notation" onchange="render_output()"></td><td>Sci.</td></tr></table></label></td><td><label class="flag_container" title="Decimal exponent style"><table><tr><td><input type="checkbox" class="flag" id="decimal_exponent" onchange="render_output()"></td><td>Dec.</td></tr></table></label></td><td><label class="flag_container" title="Ascending order"><table><tr><td><input type="checkbox" class="flag" id="poly_ascending" onchange="render_output()"></td><td>Asc.</td></tr></table></label></td><td><select id="poly_mode" title="Polynomial style" onchange="render_output()"><option value="disp">Display</option><option value="text">Text</option><option value="prog">Program</option><option value="list">List</option></select></td></tr></table></td></tr></table></td></tr></table></span><div id="status_container"><span id="status" loading>Loading...</span></div><link rel="stylesheet" type="text/css" href="https://gist.githack.com/anonymous/6059e31443745ba122dd/raw/9ca2667d0027fc4c4764533098885a8c0cc31674/poly.css"><!--[if lte IE 8]><script language="javascript" type="text/javascript" src="http://www.flotcharts.org/flot/excanvas.min.js"></script><![endif]--><script language="javascript" type="text/javascript" src="http://www.flotcharts.org/flot/jquery.js"></script><script language="javascript" type="text/javascript" src="http://www.flotcharts.org/flot/jquery.flot.js"></script><script async type="text/javascript" src="https://gist.githack.com/anonymous/6059e31443745ba122dd/raw/aa24abd74de60be00eb3d5b4cbb4e39ee8cbf3d6/poly.js"></script>

Sandbox Notes

The "no functions that perform this specific task" rule seems to be too ambiguous after all. I'm returning this to the sandbox for now.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Challenge or not, your code snippet is a mighty useful tool for math impaired people like me :). \$\endgroup\$
    – user16991
    Feb 7 '15 at 18:01
  • \$\begingroup\$ "You may not use any function that performs this specific task." But functions which perform symbolic integration, enumerate families of orthogonal polynomials, or solve systems of linear equations are ok? \$\endgroup\$ Feb 7 '15 at 18:46
  • \$\begingroup\$ @PeterTaylor I'm still mulling it over. I tried coming up with a list of no-no functions but it ended up too long. I'm aware that with the current spec Mathematica folks are going to have a field day :) \$\endgroup\$
    – Ell
    Feb 7 '15 at 19:03
  • \$\begingroup\$ Is it allowed to examine the function in ways other than numerically evaluating it? \$\endgroup\$
    – feersum
    Feb 8 '15 at 0:38
  • \$\begingroup\$ @feersum Assuming you mean something like inspecting the string or doing some symbolic analysis, then yes, that's ok. Like I said to Peter, though, I might disallow some builtin functions, like integration (symbolic or otherwise). \$\endgroup\$
    – Ell
    Feb 8 '15 at 13:06
4
\$\begingroup\$

Programming Puzzle or Code Golf?

(A judging books by covers question)

^Might need a better title.

This question is based off the "Let's Judge Some Books By Their Covers" question.

Browsing the site, I see that 1859 of our 2692 questions (69%) are tagged . My question is: what's the difference?

Your goal is to write a program (or function) to predict, given only the title of a question, whether or not that question is tagged code-golf. Your program will receive a title as input and should output either a truthy (if it's code golf) or falsey (it it's not) value.

Additionally, your program should contain no more than 1000 bytes.

Scoring

The test data will be all of the questions on this website, excluding closed/migrated/deleted questions. Your score will be the Phi coefficient calculated by comparing the results of your program with the actual data. Higher values (closer to 1) are considered better.

The Phi coefficient is calculated via the following formula:

                actual
guess      puzzle  golf  total
  puzzle   A       B     Y
  golf     C       D     Z
  total    W       X

Phi = (AD - CB) / sqrt(WXYZ)

The benefit of this scoring method is that any form of random guessing (output not affected by input) results in an average score of zero.

The exact data set is yet to be generated.

Notes

I believe this challenge is an improvement over the previous challenge due to a few reasons:

  • The question title probably has a much stronger relationship to its tags than to votes, so there's hopefully more room for improvement and competition.
  • Although there will be special-casing (for words like "short") it won't be for single questions. There's no massive outliers in the data.
\$\endgroup\$
3
  • \$\begingroup\$ You might want to force the program to be deterministic to prevent return rand<.69 \$\endgroup\$ Nov 11 '14 at 15:59
  • 2
    \$\begingroup\$ Please don't change the title, it's perfect :P \$\endgroup\$ Nov 11 '14 at 16:36
  • \$\begingroup\$ This has the issue of hardcoding. A near-perfect program can probably be written by compressing the 2692 bits needed into a 337-bytes magic string and using a hash table with enough expansion to make collisions rare. Ideally, you'd have a secret test set that's separate from the training set, but I don't know how to restrict that here except for "honor system" given that the data is public. \$\endgroup\$
    – xnor
    Nov 14 '14 at 10:22
4
\$\begingroup\$

Find a Diagonal

Given a (possibly concave) polygon of n ≥ 4 sides, output a valid diagonal, a line segment joining two distinct vertices which, aside from the endpoints, is completely contained within the interior of the polygon.

For example, for the polygon

[(0, 0), (3, 0), (1, 1), (0, 4)]

a valid diagonal (in fact, the only possible diagonal) is:

[(0, 0), (1, 1)]

Diagonal

Some invalid diagonals are:

[(3, 0), (0, 4)]     Lies outside the polygon
[(0, 0), (3, 0)]     Is an edge of the polygon - the interior of the line is not inside
[(0, 0), (0, 0)]     Two identical vertices

Input/output

Input will be n pairs of integers representing the vertices of the polygon in order. There is no fixed orientation for the input — it could be clockwise or anticlockwise. You may write either a function or a full program for this challenge, and assume any clear (all integers distinguishable) and convenient list/string format for the input.

You may assume that no three consecutive vertices of the polygon are collinear, i.e. there are no 180 degree angles. You may also assume that all coordinates are between 0 and 255 inclusive.

Output will be 2 pairs of integers representing a diagonal, which may also be in any clear and convenient list/string format.

Rules

  • You must work in the integers or rationals. In particular, you cannot use floating point integers, due to imprecision.

  • You may not use any polygon-related builtins.

  • This is code-golf, so the program in the fewest bytes wins.

Test cases

For each case, the first line is the input polygon, and the second line is all possible edges which are a valid diagonal. You only need to output one valid diagonal, and the vertices may be in either order.

Vertical diagonal
[(0, 0), (1, 1), (2, 0), (1, 3)]
[(1, 1), (1, 3)]

Horizontal diagonal
[(5, 0), (3, 4), (8, 8), (6, 4)]
[(3, 4), (6, 4)]

The relevant images are given below, in test case order (click the thumbnails to view).

Test 1 Test 2

(More cases to be added)

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Your first example of a valid diagonal has one end-point which isn't actually a vertex of the polygon. The example would benefit from an image. Since you're restricting people to exact arithmetic, you should specify a bound on the vertex coordinate values so that people can work out whether they're at risk of overflow. \$\endgroup\$ Mar 17 '15 at 8:00
4
\$\begingroup\$

The Predator of my Predator is my Prey

(Three Team KotH)

Three teams: Red, Green, Blue

  • Red kills Green
  • Green kills Blue
  • Blue kills Red

As in Red vs Blue, each entrant is assigned a colour based on their userid. Your objective is to ensure your team has the most surviving members at the end of the game.

The rules are simple but the dynamics may not be obvious. For example, wiping out your prey colour early on seems like success, but it leaves your predator colour with no predators of their own, and free to wipe you out. This means early on it may be better to herd your prey rather than kill them, but this could back-fire if your team leaves it too late...

Possible game styles

Whatever the style, when a Red bot touches a Green bot, the Green bot becomes a Red bot (the bot's code is replaced by its attacker's code). The total number of bots is therefore constant throughout the game. There are a number of settings in which such a game could be played:

  • pixels in an open arena (like Red vs Blue)

  • pixels in an arena with obstacles/walls/mazes

  • bots in a continuous arena (no grid), free to turn smoothly through 360 degrees

I like the idea of a continuous arena, and bots only seeing a small radius semi-disc ahead of them. With no vision behind them they would have to either turn regularly, or coordinate with their team mates to get more information on their surroundings. Bots would be able to write messages and read the messages of other bots on the same team.


Sandbox questions

  • Stack Snippet / full multi-language KotH?

  • which of the game styles suggested would be most interesting?

\$\endgroup\$
1
4 5
6
7 8
119

You must log in to answer this question.

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