Calculator Community > Community Contests

Code Golf: The Reboot #4

(1/3) > >>

Juju:
Welcome to this week's Code Golf: The Reboot, the fourth incarnation of the challenge hosted by myself, Juju. Not @pimathbrainiac, @c4ooo nor @JWinslow23, the one and only @Juju. I have a situation for you tonight. Let's say you have a car. Unfortunately, you left your set of keys on the seat, and the car is locked. "Oh no, I locked my keith inside", you say, with a strong lisp. However, your car came with a numerical lock, five (5) keys numbered from 1 to 5 that can replace your keys if needed, no need to call the AAA, OnStar or whatever it's called in your country. The car is rather new and you didn't had time to check the manual for the default code and how to set it, but you know the code is four (4) numbers long and the lock checks after every keypress, as in, if you enter successively 1-2-3-4-5-1, it checks against the codes 1234, 2345 and 3451. You don't really have the time to try every combination one after the other, but you know of a sequence that will check against every code successively in a minimal number of keypresses, the de Bruijn sequence, as it's called. You have your calc/smartphone/laptop on you, as you've been taught to carry no less than 5 computers on you at all times, like a sensible person, so you write a little program to compute such a sequence and try it out.

Here's a sample output:

--- Code: ---11112111311141115112211231124112511321133113411351142114311441145115211531154115
51212131214121512221223122412251232123312341235124212431244124512521253125412551
31314131513221323132413251332133313341335134213431344134513521353135413551414151
42214231424142514321433143414351442144314441445145214531454145515152215231524152
51532153315341535154215431544154515521553155415552222322242225223322342235224322
44224522532254225523232423252333233423352343234423452353235423552424252433243424
35244324442445245324542455252533253425352543254425452553255425553333433353344334
53354335534343534443445345434553535443545355435554444544554545555
--- End code ---

The cyclic sequence (as in, it wraps around so at the end it's really ...4555511112...) should contain every 4-number sub-sequence as described above exactly once per cycle. Your output don't have to be exactly this, as in there's many, many sequences with the above properties, but it should have the same length. Also, no newlines other than where it should wrap around on the screen (I've put some here because it would mess up this post, don't do that at home). Your challenge is, of course, write the smallest program that generates such sequence. If the sequence don't fit it all on the screen, like on calcs, you can implement a pager (like less on UNIX systems) or output a string that can be scrolled, or anything that could work, be sure to ask me if you're not sure and tell instructions if it's not immediately obvious or requires user action.

All the usual rules applies, like no loopholes. All non-calc languages will be scored with this counter I wrote for your convenience. Assembly and compiled Axe programs will be scored on binary size (minus the header), and TI-BASIC will be scored on on-calc source size (again, minus the header). PM me with your submission on Omnimaga and/or CodeWalrus, on every private messaging system you know you can reach me or if you know where I live or know me IRL, bring me a 3.5" floppy disk with the source enclosed. (Seriously, that would be epic and would definitely allow you a bonus.) I'll also count out the number of keypresses it took you to get to a particular code I won't disclose until the end, but it's just for fun :P And if you wanna get involved, I suggest you to check this thread.

Good luck and have fun! You have until next Sunday, 11:59:59 PM EDT.

Next week with @JWinslow23, you found your keys, but you can't figure out which one it is...

Scores
 
Language Ranking
RankLangUserSizeDateCode1Ruby@Juju1632015/06/22 15:29:00Spoiler For Spoiler:
--- Code: ---
--- End code ---
[/spoiler]



Ruby
RankUserSizeDate1Juju1632015/06/22 15:29:00
Unfortunately, no one submitted any entry, no one got the key... And I win by default, apparently. I'll post my code soon, and you still can submit an entry at a later date.

Scipi:
I might not be able to submit an entry because I have no idea how to generate de Bruijn sequences XD

I'll still make an attempt, though

Juju:

--- Quote from: Scipi on June 22, 2015, 08:52:07 pm ---I might not be able to submit an entry because I have no idea how to generate de Bruijn sequences XD

I'll still make an attempt, though

--- End quote ---
There's a lot of code and algorithms over the internet that generates de Bruijn sequences, I know it's kinda hard to come up with an algorithm yourself, so check one that already exists, study it and make your own golfed implementation. That's kind of the point. The Wikipedia page for the sequence describes a Python implementation, I think it's a good starting point.

Runer112:
For those who want to test their solutions, you can feed your result to this program. It will output each sequence that shows up more than once or not at all with a list of the indices at which it shows up. Note that the program may take a few seconds to complete; when it's done, the "Run" button will be re-enabled.

For example, here's the output I get by deleting a random character from the example output in the first post:

--- Code: ---1441 [58 271]
1442 ""
2144 ""
4144 [273 281]
4214 ""
4414 [272 280]
4421 ""

--- End code ---

Juju:
Reminder that I only recieved one entry. And it's mine. ._.

Navigation

[0] Message Index

[#] Next page