Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The challenge

The program must return a valid sequence of numbers into some rules

Rules

  • x is the size of the sequence;
  • x cannot be less than 4 or greater than 9 (Thanks David Carraher);
  • Digits of the sentence can't repeat, each one must appear once;
  • All digits between 1 to x must be in the sequence;
  • A valid sequence never begins nor ends with 1 or x;
  • Into the sequence, numbers can never appear "together";

Examples

If x=4:
2413 valid
3142 valid

1423 not valid, because begins with 1 and 23 are "together".
2134 not valid, because ends with x and 34 are "together".

Still don't get it? Other example:

If x=8:
28375146 valid, because don't start with 1 nor x(8), don't end with 1 nor x, and no numbers are "together"(no numbers touches, no numbers are the next or previous)

Sorry, I really don't know how to explain the last rule. Hope the example make it understandable.

Additional Information

  • x does not need to be an input, you can show the outputs for x=4 and x=9 working;
  • Since any language will be accepted and, I don't know how all of them work, I will ask you people to help me with this;
  • The winner will be the one who got more up-votes in 1 week, so please, vote the answer you find the best; I will mark it as the Correct one;

Good, luck. =)

share|improve this question
    
Is it correct to assume that x can not be greater than 9? –  David Carraher Sep 17 '12 at 2:59
    
Sure, forgot it but already edited. Thanks! –  BernaMariano Sep 17 '12 at 3:01
    
23 are together; Are 32 together? –  David Carraher Sep 17 '12 at 3:02
1  
I recommend you amend the challenge to allow for numbers greater than 9. (Otherwise it is trivial to solve. Consider 952647183, for example.) You can make the challenge much harder by requiring that the answer be given as a list. E.g. {2,4,1,3} –  David Carraher Sep 17 '12 at 3:35
1  
How is input provided and what is the winning criteria? –  ardnew Sep 17 '12 at 16:15

9 Answers 9

up vote 3 down vote accepted

GolfScript (17 16 chars)

Assuming input on stdin and output on stdout.

~:^),(;{-2\^%?}$

Almost alphanumeric-free...

share|improve this answer
    
Oct 31, 2011: Happy Halloween! '?' operator now works correctly for finding substrings in strings, or strings in arrays. Thank you Peter Taylor! Omg Who are you? –  BernaMariano Sep 17 '12 at 22:23
    
+1 for beating my entry. :) –  Ilmari Karonen Sep 17 '12 at 23:30
    
@BernaMariano, that was a pretty small patch. I just happened to notice someone else's question on StackOverflow and realise that string string ? or string array ? could never return anything useful, so I proposed making them do something slightly different. –  Peter Taylor Sep 18 '12 at 5:26
    
@PeterTaylor Hahahah my next challenge I will add a rule: "Peter Taylor is not allowed to answer" hahaha –  BernaMariano Sep 20 '12 at 20:13

Mathematica 38

This simply returns the digits less than or equal to x, in the order in which they appear below.

Row@Select[{2, 9, 6, 4, 7, 1, 8, 5, 3},#<x+1&]

The results from 4 through 9:

output

share|improve this answer
    
When x=9 the output breaks a rule, the sequence starts with 9 –  BernaMariano Sep 18 '12 at 22:25
    
Good catch. I missed that rule. That means that the answer for 5 also doesn't work. –  David Carraher Sep 18 '12 at 23:18

May I try to answer my own challenge?

Javascript (35 chars)

a="1";for(i=x;i>1;i--)a=i%2?a+i:i+a

Outputs

document.write(a);

4 => 2413
5 => 24153
6 => 246153
7 => 2461753
8 => 24681753
9 => 246819753
share|improve this answer
    
Surely i%2?a+=i:a=i+a can be shortened to a=i%2?a+i:i+a? And i>=2 is trivially i>1 –  Peter Taylor Sep 19 '12 at 9:45
    
@PeterTaylor Thanks! Actually I tried a=i%2?a+i:i+a but maybe I was doing something wrong because it didn't work, but I did tried this way... The i>1 you are totally right, my bad :P Already edited, now you can vote it up haha –  BernaMariano Sep 20 '12 at 3:11

Haskell 78

a 4=[3,1,4,2]
a x=let b=filter even [1..x]++filter odd[1..x]in tail b++[b!!0]

This defines a function a that takes one parameter, the desired length of the sequence. This function returns a list of numbers in that sequence. I believe this works for x >= 4

This can probably be golfed further (I don't have that much experience in haskell)

Example (in ghci)

ghci> a 4
[3,1,4,2]
ghci> a 9
[4,6,8,1,3,5,7,9,2]

Haskell 25

This version is from before a rule change that now requires that every digit from 1 to x be used exactly once in the sequence

This should work for any sequence of length > 2 (even though the rules only required 4 <= x <= 9)

putStrLn$take x$cycle"02"

Input

The number of digits in the sequence is stored in x.

Output

x = 6 :: Int

020202

x = 4 :: Int

0202
share|improve this answer
    
A recent rule change made this solution wrong. I will fix it soon. –  Matt Sep 17 '12 at 12:25
    
Looking forward your fix, @Matt! –  BernaMariano Sep 17 '12 at 12:28

PHP, 64

If I understand the rules correctly, this should work:

for($i=1;$i<=$x;$i++)echo($x%2?2*$i%$x+1:2*$i-($x+1)*($i>$x/2));

If x is odd, this simply cycles through multiples of 2 % x + 1 to produce sequences like 357924681. If x is even, this does the same, but halfway through subtracts 1+x because 2i%x+1 would otherwise never produce even values.

share|improve this answer
    
sequences like 357924681 - that one's invalid, because it ends in 1. –  Peter Taylor Sep 17 '12 at 14:48
    
Ah, ok. I thought it could only not begin in 1. In that case, this type of solution will not work. –  scleaver Sep 17 '12 at 14:49
    
There is a similar approach which works: count down in odd numbers to 1; then have the largest number; then count up in even numbers from 2. –  Peter Taylor Sep 17 '12 at 14:51
    
I was hoping to utilize non-trivial generators of the set Z/xZ so that I didn't have to use too many branches. –  scleaver Sep 17 '12 at 14:56

GolfScript, 22 20 chars

~.1|,.+2%(;(@.1&,~;\

Outputs the following sequences for the inputs 4 through 9:

2413
41352
246135
4613572
24681357
468135792

For even inputs, just ~),.+2%(; would suffice. I'm not too happy with the kluge for handling odd input values; there's got to be a more efficient way to do it.

Edit: Saved two chars by changing the output for odd inputs a bit and playing silly stack manipulation tricks. Still not too happy with the length.

share|improve this answer
    
I really don't get this GolfScript, how can I compile and run this? –  BernaMariano Sep 17 '12 at 16:07
    
Download the interpreter (a Ruby script) from this site and run it e.g. like this: echo 9 | ruby golfscript.rb program.gs, where program.gs contains the code above. –  Ilmari Karonen Sep 17 '12 at 16:16
    
You can also check out the GolfScript Interpreter too. –  mdeitrick Sep 17 '12 at 20:38
    
@Mike: ...but if you do, you'll need to hardcode the input into the program (e.g. by prepending ;"INPUT GOES HERE" to the code), since that interpreter doesn't seem to provide a separate field for input. –  Ilmari Karonen Sep 17 '12 at 20:47
    
@IlmariKaronen, I still don't get it, the echo 9 | ruby golfscript.rb program.gs thing... =( –  BernaMariano Sep 17 '12 at 22:28

Python, 37

range(3,x+1,2)+[1]+range(4,x+1,2)+[2])

http://ideone.com/xK40m

share|improve this answer

Perl 96 chars (obsolete solution since the new rules)

For what I can understand from the rules, we can assume that X is predefined. Then this solution should work :

for(2x$x..9x$x){if(!/^$x/+/$x$/+/1$/){$L=0;map{$d=$L-$_;abs$d>1||next;$L=$_}split//;print;exit}}

which is 96 characters long, although the algorithm is very naive.

It gives the following solutions :

2
30
240
2402
24020
240202
2402020
24020202
240202020

Thus, it seems obvious than there is room to a much simpler program which directly computes a solution of this form...


The following program outputs all valid sequences with any given length X (takes X in STDIN)

$x=<>;$b=10**$x;for($b/10..$b-1){if(!/^$x/+/$x$/+/1$/){$L=0;map{$d=$L-$_;abs$d>1||next;$L=$_}split//;print"$_
"}}

If you want to output ALL possible solutions (for any X), then the program becomes (102 chars) :

for(;;){$x=length$_++;if(!/^$x/+/$x$/+/1$/){$L=0;map{$d=$L-$_;abs$d>1||next;$L=$_}split//;print"$_
"}}
share|improve this answer
    
You updated your solution, but it doesn't follow all the rules. (Your old solution was posted before the rule change) specifically All digits between 1 to x must be in the sequence –  Matt Sep 18 '12 at 11:30
    
Hey, you're right. This is a huge change ! How are we supposed to play on a moving ground ? ^^ Ok, I'll update my solution if I get some time... –  Orabîg Sep 18 '12 at 17:29
    
Yeah I'm sorry for not pointing this rule, actually I thought that by just mentioning some examples it would be visible, my fault. –  BernaMariano Sep 18 '12 at 18:01

Python,30:

' 3579'[:(1+x)/2]+'1468'[:x/2]+'2' 

http://ideone.com/3csRh

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.