CODEWITHSUNDEEP
arraysalgorithmocaml
v1t0
v1t0

Reputation: 23

Creating list from array elements, making sequence of numbers

Here's the problem: I've got numbers like (for example) 3333 222 111. I need to write a program to check if it is possible to make sequence where same numbers are not each others neighbors. Only condition is that first and last elements are known. In this example lets make it 2 and 3. Correct sequence could be 2 32132131 3.

My idea was to put count of middle elements into an array [|3;2;3|], create list via while loop (one method for ascending and another for descending), add first and last element and then check if sequence is correct. There would be a few options in main method - descengind, ascending, reverted etc

Heres some code 

let makeUp b e arr k= 
  let l = ref [] in
  let i = ref 0 in
  while (List.length !l<k) do
    if arr.(!i) > 0 then l := !i+1 :: !l ; arr.(!i) <- arr.(!i) -1;
    i := (!i + 1) mod Array.length arr; 
  done;
  [b]@(List.rev !l)@[e];;

let rec isCorrect lista =
  match lista with
    [] -> true
  |h::[] -> true
  |h::t -> if (h = List.hd t)then false
    else isCorrect t;;

The problem is that I'm modyfing content of an array so I can make list of it only once. Something like this:

let find b e array length = 
  if isCorrect(makeUp b e array length) then makeUp b e array length
  else if isCorrect.....
  else [0]

simply won't work. I have no idea how to solve this task at all.

Upvotes: 1

Views: 137

Answers (2)

ivg
ivg

Reputation: 35260

Well, to solve you problem in particular, you can use Array.copy, that will create a fresh new copy of an array, like this:

let makeUp b e arr k =
  let arr = Array.copy arr in
  ...

Also, try to not be so imperative and code in more functional style. Don't use while loops and use recursion (or co-recursion) instead to build things.

For example this is a mechanical transformation (I didn't try to understand your algorithm) of your while-loop code, to a more functional:

let make b e arr k =
  let arr = Array.copy arr in
  let rec loop xs i len =
    let j = (i + 1) mod Array.length arr in
    if i = k then List.rev (e::xs)
    else if arr.(i) > 0
    then
      let () = arr.(i) <- arr.(i) - 1 in
      loop (i + 1 :: xs) j (len + 1)
    else loop xs j len in
  loop [b] 1 1

It has a slight difference though, according to the formating of your code I assume, that you thin that in expression:

 if arr.(!i) > 0 then l := !i+1 :: !l ; arr.(!i) <- arr.(!i) -1;

Both assignments will be called under the if guard, in fact, if you will use any tool that indent OCaml correctly you will see that you're wrong:

if arr.(!i) > 0 then
  l := !i+1 :: !l;
arr.(!i) <- arr.(!i) - 1;
i := (!i + 1) mod Array.length arr;

Only the assignment to the the variable l will be performed under the guard. So actually what you want is:

if arr.(!i) > 0 then begin
   l := !i+1 :: !l;
   arr.(!i) <- arr.(!i) - 1;
end;
i := (!i + 1) mod Array.length arr;

Upvotes: 0

גלעד ברקן
גלעד ברקן

Reputation: 23945

If you have the list sorted in descending order of the cardinality of each element set, couldn't you just keep interspersing the inverted pyramid?

Isn't the only time you could not create such a sequence is if one element appears in greater number (+1) than all others combined?

3333 222 111

3 3 3 3
 2 2 2
1 1 1


33333333 222 111

3 3 3 3 3 3 3 3
 2 2 2 1 1 1 x

Upvotes: 1

Related Questions