sgchris
BAN USERfunction findPath($fld, $src, $dst, &$visited = array()) {
// check if reached destination
if ($src['x'] == $dst['x'] && $src['y'] == $dst['y']) return [['x' => $src['x'], 'y' => $src['y']]];
// check if in the borders
if ($src['x'] < 0 || $src['x'] >= count($fld[0])) return false;
if ($src['y'] < 0 || $src['y'] >= count($fld)) return false;
// check if not "0" cell
if ($fld[$src['y']][$src['x']] == 0) return false;
// check if visited
$srcKey = "{$src['x']},{$src['y']}";
if (isset($visited[$srcKey])) return false;
// mark this cell as visited
$visited[$srcKey] = true;
// check children
$minPath = [];
$path = findPath($fld, ['x' => $src['x'] - 1, 'y' => $src['y']], $dst, $visited);
if ($path !== false && (empty($minPath) || count($path) < count($minPath))) $minPath = $path;
$path = findPath($fld, ['x' => $src['x'] + 1, 'y' => $src['y']], $dst, $visited);
if ($path !== false && (empty($minPath) || count($path) < count($minPath))) $minPath = $path;
$path = findPath($fld, ['x' => $src['x'], 'y' => $src['y'] + 1], $dst, $visited);
if ($path !== false && (empty($minPath) || count($path) < count($minPath))) $minPath = $path;
$path = findPath($fld, ['x' => $src['x'], 'y' => $src['y'] - 1], $dst, $visited);
if ($path !== false && (empty($minPath) || count($path) < count($minPath))) $minPath = $path;
if (!empty($minPath)) {
$minPath[] = $src;
return $minPath;
} else {
return false;
}
}
<?php
// check if a string is a polyndrome
function isPoly($str) {
$str = preg_replace('/[^A-Za-z0-9]+/i', '', $str);
$result = (strcasecmp($str, implode('', array_reverse(str_split($str)))) == 0);
return $result;
}
// check if a string (without up to K chars) is a polyndrome
function checkPoly($str, $k) {
if (!$str) return false;
$len = strlen($str);
// check 0000 to 1111 (str length bits), when it's 1, replace that char in a space
$maxNum = pow(2, $len) - 1;
for ($i = 0; $i < $maxNum; ++$i) {
$binStr = sprintf("%0{$len}b", $i);
// check that the number of "1"s in the number doesn't exceed K
if (substr_count($binStr, '1') > $k) continue;
// replace chars to space in the same indexes as "1"s in the binary number
$tmpStr = $str;
foreach (str_split($binStr) as $j => $bit) {
if ($bit == '1') $tmpStr = substr_replace($tmpStr, ' ', $j, 1);
}
// check if the newly created char is a polyndrome
if (isPoly($tmpStr)) return true;
}
return false;
}
$str = 'abcXYZbca';
$k = 3;
$res = checkPoly($str, $k);
echo "checking '{$str}', k = {$k}, result = ", ($res?'true':'false'), "\n";
<?php
function getVariants($arr, $path = [], &$list = []) {
if (empty($arr)) return $list;
if (count($path) == 3) {
if ($path[0] < $path[1] && $path[1] < $path[2]) {
if (!isset( $list[implode('+', $path)] )) {
$list[implode('+', $path)] = $path;
}
}
return $list;
}
foreach ($arr as $num) {
if (!in_array($num, $path)) {
getVariants($arr, array_merge($path, [$num]), $list);
}
}
return $list;
}
// check that the array has a + b = c
function checkABC($arr) {
$path = [];
$list = [];
$variants = getVariants($arr, $path, $list);
foreach ($variants as $vKey => $variant) {
if ($variant[0] + $variant[1] == $variant[2]) {
echo "the case is ", $vKey, "\n";
return true;
}
}
}
$arr = [1, 15, 6, 2, 9, 12];
checkABC($arr);
book the first hour of the first film ($occ array ["hour" => "movie_name"]), and make a recursive call, with attempt to book the next movie. If failing to book, try the next hour. Do this until reaching the last movie and booking it successfully.
- sgchris January 19, 2018