4
\$\begingroup\$

Write a program that takes a sorted integer array, shuffles all the elements in such a way that for every i there must exist a j such that, one of the following is satisfied:

a[i] < a[j] < a[i+1] 
a[i] > a[j] > a[i+1]

i and j are within the bounds of array.

If there are not many distinct elements, you must show an error.

For example,

Input: 1, 2
Output: Error

Input: 1, 2, 3, 4, 5, 6, 7
Output: 7, 1, 4, 2, 5, 3, 6

Input: 1, 2, 2, 4, 5, 6, 7
Output: 1, 4, 6, 2, 5, 2, 7 

Input: 1, 2, 2, 3
Output: Error

Input: 1, 5, 7, 7, 11
Output: Error

There may be more than one possible correctly shuffled arrays. You just have to solve for 1 correct solution.

Input array can have repeated elements, this requirement makes the solution tricky, otherwise a sort and skip would have worked.

Being able to have duplicates in input also makes it different from The Strange Unsorting Machine for Nefarious Purposes . And a correct solution is much trickier than the that.

The output must be of same size as input array and all elements from the input array must exist at some position in the output array.

How to take input: The program must take input either through console input or a simple delimited text file.

How to output: The program must output to the console.

What to output: Program must output both the input and the output array in following format

Input: 1, 2, 3, 4, 5, 6, 7
Output: 7, 1, 4, 2, 5, 3, 6 

If input cannot be shuffled as required, the output should look like

Input: 1, 2, 3
Output: Error

Shortest code (byte count) wins.

BONUS 1: Deduct 10 points from your count if your solution can work on unsorted inputs.

BONUS 2: Deduct 20 points from your count if your solution can find more than 1 (not all) solutions for the same input. To qualify for this bonus, your additional solution must not be just a reversed output of the other solution.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is essentially the same as The Strange Unsorting Machine for Nefarious Purposes \$\endgroup\$ – Peter Taylor Feb 20 '14 at 19:24
  • \$\begingroup\$ It is different because it allows duplicate items in the input. \$\endgroup\$ – microbian Feb 20 '14 at 19:28
  • \$\begingroup\$ I've a solution that works for arrays up to seven elements. Seems up to the specifications so far \$\endgroup\$ – Dr. belisarius Feb 20 '14 at 20:23
  • 1
    \$\begingroup\$ I've code that finds all solutions, the brute force way. Haskell: u c=filter(\d->and$map((a,b)->any(\x->(a<x&&x<b)||(a>x&&x>b))d)$zip d (tail d))$permutations c ... just need to do the I/O. Of course being haskell I/O is no fun \$\endgroup\$ – bazzargh Feb 20 '14 at 20:24
  • \$\begingroup\$ This question is very similar also: codegolf.stackexchange.com/questions/18306/alternating-sort. \$\endgroup\$ – Hosch250 Feb 20 '14 at 21:27
1
\$\begingroup\$

Haskell, 311276 (-30 bonus=246)

import Data.List
m=map
w=putStrLn
b=(intercalate",").(m show)
o="Output: "
z[]=[o++"Error"]
z a=m((o++).b)a
main=do
 r<-getLine
 let q=m read(words r)::[Int]
 w$"Input: "++b q
 mapM_ w$z$filter(\d->and$m(\(a,b)->any(\x->(a<x&&x<b)||(a>x&&x>b))d)$zip d(tail d))$permutations q

Compile with ghc, Run from the command line, input is a single line with space delimited numbers, eg echo 1 2 3 4|shuffle. This is a brute force solution so is quite likely to be slow for large input lists. It prints all the solutions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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