556
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

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

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3993 Answers 3993

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

Ouput Input... Forever

Problem

Given input chars, output them repeatedly forever.

Examples

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

Dedication: This is for all the tarpits out there!

Questions

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

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

Introduction

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

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

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

Example

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

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

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


int pow_1(int num) {
    return num;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

Scoring

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

Good luck!

Discussion

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

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

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

Thank you!

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

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

Open or close?

Posted here.

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

Convert prefix to infix

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

Minimum number of changed tiles to permit knight passage

Summary

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

Specification

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

Test cases

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

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

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

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

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

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

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

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

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

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

DXXX
XKXX
XXXX
XXXX

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

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

Is it a fibonacci-like sequence?

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

Fibonacci triangle

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

Gray code on N symbols

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

Resolve references in a chat discussion

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

Pairs of integers ordered by their exponentiation

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

Convert between graph representations.

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

Satisfy as many people as possible

Posted here.

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

Unshuffle my poker chips

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

Storing a band matrix

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

BitCycle Metagolf

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

Spend maximal money

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

Decipher a squashed sequence

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

Squash it ... again!

\$\endgroup\$
9
  • \$\begingroup\$ Where does 22 in the second sequence come from? Is it two adjacent digits? And are there repeats? \$\endgroup\$
    – Wheat Wizard Mod
    Jun 28 at 13:44
  • \$\begingroup\$ @WheatWizard yes, I'll make it more clear. And what do you exactly mean by repeats? 11 appears thrice in the second sequence \$\endgroup\$
    – mathcat
    Jun 28 at 13:48
  • \$\begingroup\$ I think you should explicitly mention that numbers can appear more than once. \$\endgroup\$
    – Wheat Wizard Mod
    Jun 28 at 13:52
  • \$\begingroup\$ It seems more like "squashing and de-squashing" than "squashing" lol \$\endgroup\$
    – Steffan
    Jun 28 at 19:16
  • 2
    \$\begingroup\$ Is n an input? It's not 100% clear to me. If so, I suggest standard sequence rules for each sequence (for each n). \$\endgroup\$
    – pajonk
    Jun 28 at 19:47
  • \$\begingroup\$ @Steffan yes but it's not that catchy :P \$\endgroup\$
    – mathcat
    Jun 29 at 11:51
  • \$\begingroup\$ "Leading zeroes can be removed" - I think you should say leading zeroes must be removed. Otherwise for n=2, ... 8, 9, 10, 11, ... -> ..., 89, 91, 10, 01, 11, ... -> ..., 89, 99, 91, 11, 10, 00, 01, 11, 11 which is not the same output. (an extra 0 is inserted) \$\endgroup\$
    – pxeger
    Jul 5 at 19:21
  • \$\begingroup\$ I'd also suggest changing n to a different letter, because n is used to explain the sequence rules. \$\endgroup\$
    – pxeger
    Jul 5 at 19:22
  • \$\begingroup\$ And maybe "print an infinite list of" -> "output the sequence of" to make the IO flexibility more explicit \$\endgroup\$
    – pxeger
    Jul 5 at 19:24
5
\$\begingroup\$

All\$^{\dagger}\$ 3-character expressions

\$^{\dagger}\$with some exceptions

In your golfing language of choice, given no input, output all valid 3-character expressions in that language, with the conditions described below.

An expression, for the purposes of this challenge, is a string of characters that can be evaluated to some result. An example of an expression in many languages is 1+2, which evaluates to 3. If evaluation causes an error/exception/crash (e.g. 1/0 in Python), then it should not be printed.

Expressions can also have side effects (modify the state of the program), e.g. y=2 in Ruby. These are allowed to be output but are not required. (In other words, you only need to print out referentially transparent expressions.) Similarly, any expressions that rely on the evaluation of previous expressions, e.g. a+2 (which requires that the value of a be set), are optional, unless they cause an error/crash, in which case they should not be output.

Some additional notes:

  • White space and comments do not count as part of an expression - e.g. 2 or 2#a in Python are one-character expressions, so they shouldn't be printed.

Any language that does not have the concept of expressions, or has no expressions that are 3 characters long meeting the above requirements, cannot be used for this challenge.

As per usual code golf, the shortest program (in bytes) wins.

Sandbox Questions

(This is my first challenge, so I don't really know what I'm doing, and feedback is greatly appreciated.)

I'm not sure how to deal with expressions that change the results of other expressions or change what counts as a valid expression, particularly in the case of side effects. For example, if in the language, evaluating any expressions causes an "answer" variable to be set, then all expressions have side effects and the challenge is moot.

I was considering having the condition for passing be "Your program satisfies the challenge if, after running, there are no other expressions you can evaluate.", but I'm unsure if that's a good requirement.

\$\endgroup\$
17
  • 1
    \$\begingroup\$ Nice challenge! However, bonus challenges are generally discouraged when writing challenges, so either remove the bonus, or make it another challenge. \$\endgroup\$
    – Seggan
    Jul 12 at 20:34
  • \$\begingroup\$ (See relevant meta post.) \$\endgroup\$
    – Steffan
    Jul 12 at 21:38
  • \$\begingroup\$ Might it be possible to generate programs instead of expressions for languages that don't have expressions? Also I think, that you can use code-generation tag. \$\endgroup\$
    – Jiří
    Jul 12 at 21:43
  • \$\begingroup\$ @Jiří I think that is a meaningfully different request from generating all expressions -- it could probably be a separate challenge. \$\endgroup\$
    – Adam
    Jul 12 at 22:15
  • \$\begingroup\$ @thejonymyster It doesn't lead to any footnote -- it's just indicating that there are some exceptions to the word "all" (the same way that "with an asterisk" means "some exceptions apply"). It's probably unnecessarily confusing though -- I'll change it. \$\endgroup\$
    – Adam
    Jul 12 at 22:18
  • \$\begingroup\$ I'm still concerned about how exactly to define "having side effects" -- does anyone have a better idea of how to deal with that? \$\endgroup\$
    – Adam
    Jul 12 at 22:21
  • 2
    \$\begingroup\$ Does having side effects also include printing or reading input? Also I have found following Wikipedia page which talks about expressions. Which led me to Wikipedia page about Referential transparency which had following sentence which might be the thing you are looking for: An expression is called referentially transparent if it can be replaced with its corresponding value (and vice-versa) without changing the program's behavior. \$\endgroup\$
    – Jiří
    Jul 12 at 23:00
  • 1
    \$\begingroup\$ The thing is, some languages don't have something called an "expression", like golfing languages (and others). In that case, do we just output valid programs? \$\endgroup\$
    – Steffan
    Jul 13 at 2:04
  • \$\begingroup\$ @Steffan I mentioned that in the description: "Any language that does not have the concept of expressions, or has no expressions that are 3 characters long meeting the above requirements, cannot be used for this challenge." \$\endgroup\$
    – Adam
    Jul 15 at 18:30
  • \$\begingroup\$ What is the definition of "expression" in regards of comments? Is it allowed to output strings that include comments? (e.g. 3#2 in python) \$\endgroup\$
    – Steffan
    Jul 15 at 18:39
  • \$\begingroup\$ @Steffan Hm, I'd say that's a 1-character expression with a comment, so by the rules above it shouldn't be printed. But that's not a strong conviction on my part. \$\endgroup\$
    – Adam
    Jul 15 at 18:58
  • \$\begingroup\$ Also, is it allowed to print things with whitespace, e.g. " " or " 2"? \$\endgroup\$
    – Steffan
    Jul 15 at 19:08
  • \$\begingroup\$ Also, can random warnings be spouted to stderr? \$\endgroup\$
    – Steffan
    Jul 15 at 19:11
  • \$\begingroup\$ @Steffan Thank you for asking these questions :) I'd also say that white space isn't part of the expression, except in obvious cases - e.g. the expression representing the empty string " " -- so it shouldn't be allowed. For the second point: I think I'll say that expressions generating errors that don't stop execution of the program are allowed, so yes. Those expressions probably shouldn't be required to output though (?) \$\endgroup\$
    – Adam
    Jul 15 at 19:25
  • \$\begingroup\$ For the warnings, I can actually disable them with a flag (like -W0 in ruby), so it's fine either way. So as far as spaces, " 2" isn't allowed, I guess. And - 2 isn't allowed either, I guess? Welp, this is going to add some bytes lol \$\endgroup\$
    – Steffan
    Jul 15 at 19:47
5
\$\begingroup\$

Have you heard of tralindromes?

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

Divisor of a string

\$\endgroup\$
4
  • 2
    \$\begingroup\$ May we assume the input string has positive length? \$\endgroup\$
    – pajonk
    Aug 10 at 8:31
  • 1
    \$\begingroup\$ @pajonk yes, you can \$\endgroup\$
    – badatgolf
    Aug 10 at 9:31
  • 4
    \$\begingroup\$ You may also want to specify what to expect within the string (letters, whitespace, special characters?) - I suggest only lowercase letters. \$\endgroup\$
    – pajonk
    Aug 10 at 11:25
  • 1
    \$\begingroup\$ Can the output have duplicates? Can it be in any order? \$\endgroup\$
    – Steffan
    Aug 10 at 21:30
5
\$\begingroup\$

Radiation Hardening Koth

\$\endgroup\$
5
  • \$\begingroup\$ Why not the mean? \$\endgroup\$
    – Seggan
    Aug 9 at 18:53
  • 1
    \$\begingroup\$ You could get really luckly sometimes and get paired against "almost dead" programs giving you a very high score with no real effort. Or get really unlucky and the first program in the first round guesses the single essential character in your source code. I think the median will compensate for this randomness and give a better idea of the general performance of a program. \$\endgroup\$
    – mousetail
    Aug 9 at 19:25
  • \$\begingroup\$ Ah, okay then. Got it. \$\endgroup\$
    – Seggan
    Aug 9 at 19:43
  • \$\begingroup\$ I would say multi-language koth's land up bad cuz (length) 100 is a little too much already for python but 100 is like a no-go for c++ (i guess) \$\endgroup\$ Aug 10 at 12:26
  • 1
    \$\begingroup\$ The 255 byte limit is not intended for it to be a challenge to fit your code in that space, that's pretty doable in most any language. The idea is you can't stuff your code with a gigabytes of comments to simply reduce the chance of a important character being deleted. \$\endgroup\$
    – mousetail
    Aug 10 at 12:32
4
\$\begingroup\$

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

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

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

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

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


A minimal implementation of the make (1) utility.

By minimal I mean,

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

This only leaves constructs (called rules) of the form

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

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

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

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

A target is deemed already built if

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

Otherwise it is built by

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

A prerequisite is deemed fulfilled if

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

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

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

apply.

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

Sample Input

# Babymake compatible makefile for babymake
all:babymake

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

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

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

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

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

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

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

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

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

Sample output

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

BlackJack Part II

Repost from the original sandbox

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

Rules

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

Dealing and Bot Moves

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

Programmer's Interface and Legal Moves

As documented in the CardShark class:

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

Winner Selection

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

Code Review github

Issues & ToDo

None! (no known problems at least)

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

Version History

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

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

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

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

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

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

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

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

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

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

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

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

Examples

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

How long until my next birthday is on a weekend

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

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

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

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

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

3D Maze Navigation

Output a path through a 3D maze.

Input

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

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

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

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

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

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

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

Output:

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

SSEENNDDSSWWNN

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

A couple of examples:

Input:

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

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

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

Output:

SSXEENN

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

Input:

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

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

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

Output:

I'm providing a few test cases.

Test case 1

Input

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

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

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

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

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

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

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

4 and 20 baked in a π

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

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

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

3.14159
   ^

Rules:

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

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

This is code golf, so lowest score wins.

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

ASCII ART edge detection

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

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

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

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

could became:

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

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

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

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

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

This is my sample program:

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

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

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

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

A possible output could be:

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

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

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

You must log in to answer this question.

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