Over the weekend, a local instructional tech company (Instructure) had a computer programming contest. I was down hiking in southern Utah, so I didn’t get to be a part of the coding mayhem. Up for grabs was $10,485.76. It’s an agreeable publicity trick that CEO Josh Coates has pulled before (last time it was for a company called Mozy, also in Utah County.) I previously solved one of the Mozy contest sample questions for you, and today I’ll do the same work with problem #1 of the Instructure coding challenge sample set:

Given a variable number of playing cards, form the best hand that does not exceed 21. The cards are in the set [23456789JQKA], where 2-9 are worth their face value, J Q and K are worth 10, and A can be selected to be worth either 1 and 11. In this scenario, you are only playing with one suit, so there is never more than one of each card.

Input:

The first line is a single number, which is the number of lines to follow. Each line after that is a sequence of characters in the above set.

Output:

For each input line of cards, output the highest possible score that does not exceed 21.

Example:

STDIN:

4
296J
85
A37
475A

STDOUT:

21
13
21
20

And here is my solution:

  1. function pc_array_power_set($array)
  2. {
  3.         // src: http://docstore.mik.ua/orelly/webprog/pcook/ch04_25.htm#phpckbk-CHP-4-EX-5
  4.         $results = array(array( ));
  5.         foreach ($array as $element)
  6.                 foreach ($results as $combination)
  7.                         array_push($results, array_merge(array($element), $combination));
  8.         return $results;
  9. }
  10. function CardValue($array,$aceValue=1)
  11. {
  12.         foreach($array as $key=>$card)
  13.         {
  14.                 if ($card==’J'||$card==’Q'||$card==’K')
  15.                         $newCardArray[]=10;
  16.                 else if ($card==’A')
  17.                         $newCardArray[]=$aceValue;
  18.                 else
  19.                         $newCardArray[]=$card;
  20.         }
  21.         $value=array_sum($newCardArray);
  22.         return $value;
  23. }
  24. $target=21;
  25. $input=file($argv[1]);
  26. for($x=1;$x<=trim($input[0]);$x++)
  27. {
  28.         $row=trim($input[$x]);
  29.         $cardArray=str_split($row);
  30.         $aceValue=1;
  31.         if (in_array(‘A’,$cardArray)) $aceValue=11;
  32.         $combinations=pc_array_power_set($cardArray);
  33.         $value=CardValue($cardArray);
  34.         $highest=0;
  35.         if ($value!=21)
  36.         {
  37.                 for ($y=0;$y<$aceValue;$y+=10)
  38.                 {
  39.                         foreach($combinations as $hand)
  40.                         {
  41.                                 $value=CardValue($hand,$aceValue);
  42.                                 if ($value>$highest&&$value<=$target)
  43.                                         $highest=$value;
  44.                         }
  45.                 }
  46.         }
  47.         else
  48.         {
  49.                 $highest=$value;
  50.         }
  51.         echo(“$highest\n”);
  52. }

photo credits: http://www.butterfunk.com/image-12/N.E.R.D.htm