5
\$\begingroup\$

I was asked to provide the solution of this rolling dice problem in an interview. When I showed him my solution, he said that there is another way to find the solution. I am looking for answer in PHP script only.

Question:

Two persons are playing a game of rolling 2 dices. Each person rolls the two dices n times and records the outcomes (sum of value of two dices) of all the n attempts. So after n attempts of both the player we have two list corresponding to the n outcomes of two players.

They want to know that whether they have got all possible outcomes( 1 to 12) same number of times or not. If they got all the possible outcomes same number of times then they are called lucky otherwise unlucky.

Input: Two Integer Arrays (L1, L2) corresponding to outcomes of two players.

Output: Lucky or Unlucky depending on the case

My Answer:

<?php
function rollingdice($input1,$input2)
{
  foreach($input1 as $k=>$a)
  { 
    if(in_array($a,$input2))
    {$p = array_search($a, $input2);
     unset($input2[$p]);
    }
    else
    { return 'Unlucky';}
  }
return 'Lucky';
}
?>
\$\endgroup\$
2
  • \$\begingroup\$ Couldn't you just compare the two arrays directly? Ideally after sorting. \$\endgroup\$ – Mr Wednesday Apr 22 '14 at 2:39
  • 1
    \$\begingroup\$ all possible outcomes (1 to 12) You can't roll a 1 with two dice. :) \$\endgroup\$ – Alex Howansky Jun 4 '14 at 15:32
5
\$\begingroup\$

Based on your use of in_array(), you don't appear to be concerned with the order of the elements. In that case, you can simply sort the arrays and compare them directly.

function compare($array1, $array2)
{
    sort($array1);
    sort($array2);

    return ($array1 == $array2) ? "Lucky" : "Unlucky";
}
\$\endgroup\$
0
2
\$\begingroup\$

With extra O(n) space the complexity can be made O(n) only, without sorting that will take O(nlogn)

Use a map and add a value for each key as (previousValue +1) or (previousValue - 1) based on array type A or B. Also use a counter to track an absolute increase or decrease if at end the counter is 0. Then the two array has same number of occurrence else not.

[Edited: Added code]

A java implementation

import java.util.HashMap;

public class Main {

    public static void main(String[] args) {

        HashMap<Integer, Integer> trackMap = new HashMap<>();
        int n = 6;
        int[] a = {4, 12, 4, 10, 6, 10};
        int[] b = {10, 12, 10, 4, 4, 6};
        int counter = 0;
        for (int i = 0; i < n; i++) {
            if (!trackMap.containsKey(a[i])) {
                trackMap.put(a[i], 1);
                counter++;
            } else {
                int prevVal = trackMap.get(a[i]);
                trackMap.put(a[i], prevVal + 1);
                counter = counter + ((Math.abs(prevVal) > Math.abs(prevVal + 1)) ? -1 : 1);
            }
            if (!trackMap.containsKey(b[i])) {
                trackMap.put(b[i], -1);
                counter++;
            } else {
                int prevVal2 = trackMap.get(b[i]);
                trackMap.put(b[i], prevVal2 - 1);
                counter = counter + ((Math.abs(prevVal2) > Math.abs(prevVal2 - 1)) ? -1 : 1);
            }
        }
        System.out.println(counter == 0 ? "Lucky" : "Unlucky");
    }
}

Or instead if using counter, you cand finally iterate the hashMap if all value are zero then the person is lucky else not

\$\endgroup\$
3
  • \$\begingroup\$ Would you mind demonstrating this technique so that I can be sure I understand your theory? \$\endgroup\$ – mickmackusa Jul 29 '20 at 3:39
  • \$\begingroup\$ @mickmackusa sure. Also looking if can be done using better complexity in term of space. \$\endgroup\$ – Mr AJ Jul 29 '20 at 11:10
  • 1
    \$\begingroup\$ I only code in php. I thought this was a php question. \$\endgroup\$ – mickmackusa Jul 29 '20 at 12:06
2
\$\begingroup\$

@Mr AJ already gave you a valid answer on the algorithmic approach in his Java example, but since it seems Java is unfamiliar to you, I will just write out the algorithm here in a way that hopefully makes sense to you.

There is no need to sort the arrays, doing so ensure more operational complexity than is needed here, as now your a guaranteeing that you are visiting each value in the arrays at least twice (once for sorting, once for reading out sorted values - yes this even happens under the hood in with a == comparison between two sorted arrays as happens in currently selected answer). You can achieve the goal by iterating each array a single time, such that you only visit each value once.

Your logic should be along the lines of:

  • Compare array sizes, if unequal then 'Unlucky'.
  • Iterate over first array, building a map (perhaps an associative array or stdClass object in PHP). Keys are values encountered in the array (i.e. 2-12) and the values for this map are the counts of each of the corresponding dice values. You should probably also error on condition of getting value outside the 2-12 range in the array.
  • Iterate over the second array, if a dice value is encountered that is not present as a key in the map built from first array, then 'Unlucky'. Otherwise you decrement the stored count in the map by one each time a corresponding dice value is encountered.
  • Iterate over the map values, if any value is not equal to 0 then 'Unlucky' else 'Lucky'.

This provides an O(2n) worst-case operational complexity, where n is the size of the arrays.

\$\endgroup\$
0
1
\$\begingroup\$

After reading the other answers that speak in depth on the theory and big O, I thought I would script up my interpretation.

Code: (Demo with echoed variables to show values and processes)

function roll() {
    return rand(1, 6) + rand(1, 6);
}

$roller1 = [];
$roller2 = [];
$totalRolls = 1;

for ($i = 0; $i < $totalRolls; ++$i) {
    $roller1[] = roll();
    $roller2[] = roll();
}

$map = array_count_values($roller1);
    
$outcome = 'Lucky';
foreach ($roller2 as $roll) {
    if (!empty($map[$roll])) {
        --$map[$roll];
    } else {
        $outcome = 'Unlucky';
        break;
    }
}

echo $outcome;

After the formation of the two arrays, php offers a simple function call to create the map of roll values and the number of instances of each value -- array_count_values(). This action is only necessary on the first array.

The second array is then iterated and each value is checked against the map. If the given value is not a key in the map or it is has a falsey (0) value at the key, then there is a mismatch between $roller1 and $roller2 -- the outcome is Unlucky and the loop is sensibly broken/halted. As matches are found between the map and the second array, the encountered map keys have their respective value decremented (spent) to enable the correct action with empty().

As @MikeBrant said:

This provides an O(2n) worst-case operational complexity, where n is the size of the arrays.

the worse-case scenario is the only way to achieve the Lucky outcome.

A best-case operational complexity (Unlucky outcome) where the map is generated (n) and the loop breaks on the first element in the second array (1) ...o(n+1).

As for speed, I don't know. I didn't benchmark this script against the double-sort&compare technique, but you will notice that my technique is calling array_count_values() and will make iterated empty() calls and every function call equates to some level of a performance hit (even if miniscule).

\$\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.