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.

A fragmented file is a file which is seperated into several parts on a harddrive, because it can't fit into a certain space.

On all harddrives, there are files called unmovable files, which are unmovable. To simulate real data on a harddrive, the input will also have unmovable files.

You are given several sequences of consecutive numbers, all scrambled into one list. The goal is to order each of these sequences so that they are placed in as little space as possible. The list can be as big as you need it to be. If there is no space for a sequence, then put a - instead.

To mark the unmovable files, another list, with the same length as the data, will be given after you recieve the data. It will contain either a 0 or a 1. Every 1 within that list means that the corresponding item in the data is unmovable.

Shortest code wins.

Test Cases

The output does not have to be exactly like this, but the length needs to be the same, and all of the sequences need to be ordered.

[ 0,  0,  1,  1,  1,  1,  0,  0,  0,  0,  0]
[25, 30, 11, 12, 13, 14, 68, 69, 31, 26, 32]
Output: [25, 26, 11, 12, 13, 14, 68, 69, 30, 31, 32]
(output length: 11)

[0, 0, 0,  0, 0,  1,  1,  1, 0, 0,  0,  0,  0,  0,  0, 0]
[2, 3, 5, 14, 8, 10, 11, 12, 4, 6, 28, 30, 29, 15, 16, 7]
Output: [14, 15, 16, -, -, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 28, 29, 30]
(output length: 18)
share|improve this question
    
If some part of the challenge is not explained well, tell me! I cannot explain things well. –  beary605 Dec 5 '12 at 5:17
2  
Yes, the rule telling how we are supposed to eliminate some sequence is not clear (why the 8 instead of the 2 in last example). Also the fact that 15 is present twice in the last array is confusing me... –  Orabîg Dec 5 '12 at 7:50
    
@Orabîg: ! The last example has a lot of mistakes. I'll fix that. –  beary605 Dec 5 '12 at 20:45
    
In the 2nd example, the output length still isn't equal to the input length? Am I misunderstanding? Is the hard drive growing? –  marinus Dec 6 '12 at 0:21
1  
@beary605: You might want to put that in your question. It's not obvious. –  marinus Dec 6 '12 at 0:49

2 Answers 2

up vote 5 down vote accepted

APL (132 126 123 147 145 143)

This was a bit harder than I thought it'd be :)

Edit: the hard drive is infinite :S. All sequences that could not fit in the original space, are now appended onto the end of the output.

F←⍬⋄{×⍴⍵:∇1↓⍵⊣{∨/P←S⍷⍨1⍴⍨⍴⍵:S[R]∘←0⊣D[R←1-⍨(⍳⍴⍵)+⌊/P/⍳⍴P]∘←⍵⋄F∘←F,⍵}⊃⍵⋄D[S/⍳⍴S]∘←'-'}G[⍒⊃∘⍴¨G←K⊂⍨1≠|-⌿K,[÷2]¯1⌽K←K[⍋K←(S←~⎕)/D←⎕]]⋄F,⍨D/⍨~⌽∧\⌽S

This is what it does to your 1st and 2nd example (the 2nd example is different, but in your example the output length is not the same as the input length and you said in a comment it was wrong, so...)

⎕:    25 30 11 12 13 14 68 69 31 26 32
⎕:    0  0  1  1  1  1  0  0  0  0  0 
25 26 11 12 13 14 30 31 32 68 69
⎕:    2 3 5 14 8 10 11 12 4 6 28 30 29 15 16 7
⎕:    0 0 0 0  0 1  1  1  0 0 0  0  0  0  0  0
14 15 16 - - 10 11 12 2 3 4 5 6 7 8 28 29 30

Explanation:

  • F←⍬: set F to the empty list. This will hold the overflow.
  • K←K[⍋K←(S←~⎕)/D←⎕]: read two lists. The first list (numbers) is stored in D. The second list (whether the data is unmovable) is inverted and then stored in S. Get all movable numbers, and sort them. Store this in K.
  • G←K⊂⍨1≠|-⌿K,[÷2]¯1⌽K: Subtract each element of K from the next element of K. Wherever this is not 1, we found the beginning of a new sequence. Store the list of sequences in G.
  • G[⍒⊃∘⍴¨G...]: sort the list of sequences by descending length. This way, we place the longest sequences first.
  • {×⍴⍵:...}G: as long as this list of sequences is not empty...
  • ∇1↓⍵⊣: handle the tail of the list, after...
  • {...}⊃⍵: doing the following with the head:
  • ∨/P←S⍷⍨1⍴⍨⍴⍵: find, in S, a list of ones that is as long as the current sequence ().
  • S[R]∘←0⊣D[R←1-⍨(⍳⍴⍵)+⌊/P/⍳⍴P]∘←⍵: if there is one, store in D at the first position that it fits, and mark these positions as unmovable in S.
  • ⋄F∘←F,⍵: if there is no room, add it to the overflow.
  • ⋄D[S/⍳⍴S]∘←'-': when we're at the end of the list of sequences, all positions where S is still one are places where we couldn't put anything. Mark these with -.
  • ⋄F,⍨D/⍨~⌽∧\⌽S: then, at the end, display D, with the trailing -s removed, followed by the overflow (F) per the new rules.
share|improve this answer
    
wow, it was still wrong. :( Thanks for pointing that out. –  beary605 Dec 6 '12 at 0:20
    
@marinus Above you say you place the longest sequence first. If so is this optimum. What would your code do with:[0 0 0 0 0 0 1 1 1 1 0 0 0 0 0][5 2 3 14 1 17 9 10 11 12 18 16 15 7 6] –  Graham Dec 13 '12 at 14:39

I decided to tackle this solution in Scala, taking advantage of both functional and imperative features of the hybrid language. Here is the code for my solution.

def orderedSequences(filePieces: List[(Int,Int)]): List[List[(Int,Int)]] = {
  def orderedSequencesR(filePieces: List[(Int,Int)], currentSequence: List[(Int,Int)], sequences: List[List[(Int,Int)]]): List[List[(Int,Int)]] = {
    if(filePieces == Nil) sequences :+ currentSequence
    else if(currentSequence == List.empty) orderedSequencesR(filePieces.tail, List(filePieces.head), sequences)
    else if(filePieces.head._2 == currentSequence.last._2 + 1) orderedSequencesR(filePieces.tail, currentSequence :+ filePieces.head, sequences)
    else orderedSequencesR(filePieces, List.empty, sequences :+ currentSequence)
  }
  orderedSequencesR(filePieces, List.empty, List.empty)
}

def defragment(sequences: List[List[(Int,Int)]], filePieces: List[(Int,Int)]): List[Any] = {
  val largestSequenceLength = sequences.flatten.length
  var solution = scala.collection.mutable.ListBuffer[(Int,Int)]()

  filePieces foreach {filePiece => if(filePiece._1 == 1) solution += filePiece  else solution += ((-1,0))}

  solution ++ Iterator.fill(largestSequenceLength)((-1,0))

  sequences foreach {
      sequence =>
      var sequenceIsInserted = false
      var currentPosition = 0
      while(!sequenceIsInserted) {
        if(solution.slice(currentPosition,currentPosition + sequence.length).forall((s: (Int,Int)) => s._1 == -1)){
          solution = solution.slice(0,currentPosition) ++ sequence ++ solution.slice(currentPosition + sequence.length, solution.length)
          sequenceIsInserted = true
        }
        currentPosition += 1
      }
  }

  solution.map(_._2).toList
}

def getDefragmentedFiles(isUnmovable: List[Int], files: List[Int]) = {
    val filePieces = isUnmovable zip files
    val sequences = orderedSequences(filePieces.filter(os => os._1 == 0).sortBy(t => t._2))
    val bestSolution = defragment(sequences.permutations.toList.sortBy {b => defragment(b, filePieces).length}.head, filePieces)
    println(bestSolution map { case 0 => '-'; case x => x })  
}

val isUnmovable = List(0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0)
val files = List(2,3,5,14,8,10,11,12,4,6,28,30,29,15,16,7)
getDefragmentedFiles(isUnmovable, files)

I take the list of movable/unmovable positions along with the files and zip them up. I then get the movable files, sort them in order, and pass them into orderedSequences to get a list of file sequences.

Once I get the sequences, I get all the permutations of the sequences and I brute-force defrag them, taking the solution of the shortest length. This is pretty inefficient, but I can't think of a more efficient solution right now. The defrag method takes each sequence, in order, and iterates through the memory space until a valid spot to place the sequence is found.

After getting the best solution, I prettify it and print it out as a list.

share|improve this answer
    
An uncryptified answer is fine, but the question is tagged 'code golf', so you should produce a radically shortened version of the answer, and count its characters. –  user unknown Dec 19 '12 at 21:33

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.