Optimized solution for a rolling dice code puzzle

Question

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';
}
?>

• Mr Wednesday: Couldn't you just compare the two arrays directly? Ideally after sorting.
• Alex Howansky: all possible outcomes (1 to 12) You can't roll a 1 with two dice. :)

Answer 1

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";
}

Answer 2

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

• mickmackusa: Would you mind demonstrating this technique so that I can be sure I understand your theory?
• Mr X: @mickmackusa sure. Also looking if can be done using better complexity in term of space.
• mickmackusa: I only code in php. I thought this was a php question.

Answer 3

@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.

Answer 4

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).