# Optimized solution for a rolling dice code puzzle

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

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

• Couldn't you just compare the two arrays directly? Ideally after sorting. – Mr Wednesday Apr 22 '14 at 2:39
• all possible outcomes (1 to 12) You can't roll a 1 with two dice. :) – Alex Howansky Jun 4 '14 at 15:32

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


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.

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

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

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

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

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).
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}