Skip to content

Instantly share code, notes, and snippets.

@hadaytullah
Last active October 25, 2019 09:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hadaytullah/4d119147a8864ce9af01dc85e451a23b to your computer and use it in GitHub Desktop.
Save hadaytullah/4d119147a8864ce9af01dc85e451a23b to your computer and use it in GitHub Desktop.
Morse code algorithm in PHP
<? php
class MorseNode {
private $value;
private $leftNode;
private $rightNode;
function __construct($value, $leftNode, $rightNode){
$this->value = $value;
$this->leftNode = $leftNode;
$this->rightNode = $rightNode;
}
function getLeftNode(){
return $this->leftNode;
}
function getRightNode(){
return $this->rightNode;
}
function getValue(){
return $this->value;
}
}
function traverse($node, $signalsList, &$result){
//exit conditions
if(count($signalsList) == 0 ){
array_push($result,$node[0]);
return;
}
if($node[1] == null and $node[2] == null){
array_push($result,$node[0]);
return;
}
//normal flow
$signalBit = array_shift($signalsList);
switch($signalBit){
case ".": //left, 1 index
if($node[1] != null){ //leaf check
traverse($node[1],$signalsList, $result);
}
break;
case "-": //right, 2 index
if($node[2] != null){ //leaf check
traverse($node[2],$signalsList, $result);
}
break;
case "?":
if($node[1] != null){ //leaf check
traverse($node[1],$signalsList, $result);
}
if($node[2] != null){ //leaf check
traverse($node[2],$signalsList, $result);
}
break;
}
}
function possibilities ($signals) {
// the class declared above MorseNode can be used to make a more verbose but a bit slow version of the tree
// this Array form is a compact version, I will use this for efficiency reason
$morseTree = ["start",["E",["I",["S",null,null],["U",null,null]],["A",["R",null,null],["W",null,null]]],["T",["N",["D",null,null],["K",null,null]],["M",["G",null,null],["O",null,null]]]];
$signalList = str_split($signals);
$result = [];
traverse($morseTree, $signalList, $result);
return $result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment