Problem Statement
When new files are written to a hard disk, oftentimes they are broken up into fragments and stored in different physical locations on the drive. "Defragmentation" is the process of reordering these fragments such that they are all adjacent on the hard disk. Not only does this increase performance of the computer, but it helps prevent new files from being fragmented in the future.
Given a
"C.RC.C.CC..C....RCC.."
A 'C' represents a cluster on the disk, an 'R' represents a read-only cluster (one that cannot be moved), and a period ('.') represents a position on the disk which does not correspond to a file. The defragmentation algorithm reads the FAT from right to left, looking for a cluster to move. Once it finds one, it starts searching from left to right (starting at position 0) for an empty space. In the above example, the rightmost 'C' is at position 18 in the string, and the leftmost period is at position 1. The defragmenter then moves the cluster to the empty space, resulting in the new FAT below:
"CCRC.C.CC..C....RC..."
Now, the rightmost cluster is at position 17, and the leftmost empty space is at position 4. After moving this cluster, the FAT is arranged as follows:
"CCRCCC.CC..C....R...."
The next cluster is at position 16, but it is read-only and cannot be moved. Therefore, the defragmenter continues past it to the cluster at position 11, and moves it to the empty space at position 6.
"CCRCCCCCC.......R...."
When the defragmenter now tries to move the cluster at position 8, it discovers that there is no empty space to the left of 8 in which to place it. This means that defragmentation is complete. Three clusters were moved, so for this example your method would return 3.
Definition
- Class:
- Defragment
- Method:
- clustersMoved
- Parameters:
- String
- Returns:
- int
- Method signature:
- int clustersMoved(String FAT)
- (be sure your method is public)
Constraints
- FAT will contain between 1 and 50 characters, inclusive.
- FAT will contain only periods ('.') and the characters 'C' and 'R'.
Examples
"C.RC.C.CC..C....RCC.."
Returns: 3
This is the example from above.
"CCRCCCCCC.......R...."
Returns: 0
At this stage, the hard disk is already defragmented as much as possible. There are no clusters that need to be moved.
"..........CCCCCC"
Returns: 6
Each of the six clusters on the right will need to be moved to the left.
".RR...RR.RR....RR....R......R.R.RRRR.RR...RRR....."
Returns: 0
The disk is highly fragmented, but each cluster is marked as read-only, so no move operations can be performed.
"."
Returns: 0
"C"
Returns: 0
"R"
Returns: 0
".."
Returns: 0
".C"
Returns: 1
".R"
Returns: 0
"C."
Returns: 0
"CC"
Returns: 0
"CR"
Returns: 0
"R."
Returns: 0
"RC"
Returns: 0
"RR"
Returns: 0
"RR.R..C.CC..CRRRRRC.C.C.RCC..CR....RC.C.."
Returns: 7
"RRR.R...CRCCR...C.CRR.CCCR.C.CC.C.RR.C.C.RR"
Returns: 9
"C..RR.RR..C.CRRR..RCR...RC..CRR.CC...RRRRRRC."
Returns: 6
"CRRCRC.RCRRR.CCR.C.CCCCR.R....CRRR.RCRC.CR..R.R"
Returns: 4
"...C.RCRRR..RRCCCR.CCRRC.CRRCRCR.RCRCC..RCC.RCRRR"
Returns: 8
"RC...RCRR.RRRRCC.RRRCRC.C.RRC..C.RRRR..RCRCC.RCCC."
Returns: 7
"CCRC..RC.R..RRC.RRR.CR.R.RC.RCCRC.RRR.RCCRRCCRR..R"
Returns: 8
"C..RCRR..CRR..RR.C.RCR.R.CC..CRCCRCCRCCCRCC.C.CR.R"
Returns: 12
"C.RRRCR.RRC....RR.RC..R....CR.CRR.RR.CRCC.C......R"
Returns: 7
".RRCR.RCC..R...CCCC..CCRR.CR.CCR.C.R.RCC.CCCRR.RRR"
Returns: 9
".........................CCCCCCCCCCCCCCCCCCCCCCCCC"
Returns: 25
"........................CCCCCCCCCCCCCCCCCCCCCCCCCC"
Returns: 24
"........................RCCCCCCCCCCCCCCCCCCCCCCCCC"
Returns: 24
"....CCCCCCCCCCCCC"
Returns: 4
"CCCCCCCCCCCCC.C"
Returns: 1
".C"
Returns: 1
"CC"
Returns: 0
"RRRRR"
Returns: 0
"RRRRRR"
Returns: 0
"CCC"
Returns: 0
"RRRRRCRR"
Returns: 0