Java generics, convert nested list to array I have to interface to some old code using nested arrays, so I have to convert my nested Lists to nested arrays. Any idea, suggestions, improvements are warmly welcomed.

public static <E> int getNestedListMaxSize(List<List<E>> list){
    int result = 0;
    if (list != null && list.size() > 0){
        for (List<E> innerList : list){
            result = Math.max(result, innerList == null ? 0 : innerList.size());
        }
    }
    return result;
}

@SuppressWarnings("rawtypes")
public static <E> Class getNestedListClass(List<List<E>> list){
    Class result = null;
    if (list != null && list.size() > 0){
        for (List<E> innerList : list){
            if (innerList != null && innerList.size() > 0){
                result = innerList.get(0).getClass();
                break;
            }
        }
    }
    return result;
}

@SuppressWarnings({ "unchecked", "rawtypes" })
public static <E> E[][] convertNestedList(List<List<E>> list){
    E[][] result = null;
    Class clazz = getNestedListClass(list);
    if (clazz != null){
        result = (E[][]) Array.newInstance(clazz, list.size(), getNestedListMaxSize(list));

        for(int i=0; i < list.size(); i++) {
            E[] element = null;
            if (list.get(i) != null){
                E[] dummy = (E[]) Array.newInstance(clazz, list.get(i).size());
                element = list.get(i).toArray(dummy);
            }
            result[i] = element;
        }
    }
    return result;
}

public static void main(String[] args) {
    List<List<String>> list = new ArrayList<List<String>>();
    list.add(new ArrayList<String>());
    list.get(list.size()-1).add("0.0");
    list.get(list.size()-1).add("0.1");
    list.get(list.size()-1).add("0.2");
    list.add(new ArrayList<String>());
    list.get(list.size()-1).add("1.0");
    list.get(list.size()-1).add("1.1");
    list.get(list.size()-1).add("1.2");
    list.get(list.size()-1).add("1.3");
    list.add(new ArrayList<String>());
    list.get(list.size()-1).add("2.0");
    list.get(list.size()-1).add("2.1");

    String [][] array = convertNestedList(list);

    System.out.println(Arrays.deepToString(array));
}

I'd use guard clauses to check whether the list parameter is null or not. Furthermore, the list.size() > 0 check looks unnecessary in the first two methods, the result will be same if you omit it.

Anyway, are you sure that null is an acceptable parameter here? Wouldn't it better to throw an exception in this case?

public static <E> int getNestedListMaxSize(final List<List<E>> list) {
    if (list == null) {
        return 0;
    }
    int result = 0;
    for (final List<E> innerList: list) {
        if (innerList == null) {
            continue;
        }
        result = Math.max(result, innerList.size());
    }
    return result;
}

In the getNestedListClass I'd use guard clauses too and a return instead of the break.

@SuppressWarnings("rawtypes")
public static <E> Class getNestedListClass(final List<List<E>> list) {
    if (list == null) {
        return null;
    }

    for (final List<E> innerList: list) {
        if (innerList == null || innerList.isEmpty()) {
            continue;
        }
        return innerList.get(0).getClass();
    }
    return null;
}

I think the return makes the code much easier to read and follow.

In the convertNestedList method

the dummy variable should have a meaningful name, for example innerListArray,
the default value of result[i] is null, so you don't have to set it to null explicitly if the inner list is null,
list.get(i) is called three times. It could have a local variable.

public static <E> E[][] convertNestedList(final List<List<E>> list) {
    final Class<?> clazz = getNestedListClass(list);
    if (clazz == null) {
        return null;
    }
    final E[][] result = (E[][]) Array.newInstance(clazz, list.size(),
        getNestedListMaxSize(list));

    for (int i = 0; i < list.size(); i++) {
        final List<E> innerList = list.get(i);
        if (innerList == null) {
            continue;
        }
        final E[] innerListArray = (E[]) Array.newInstance(clazz, innerList.size());
        result[i] = innerList.toArray(innerListArray);
    }
    return result;
}

The main method should be a unit test method with proper assert calls:

@Test
public void testConvertNestedList() {
    final List<List<String>> list = new ArrayList<List<String>>();
    list.add(new ArrayList<String>());
    list.get(list.size() - 1).add("0.0");
    list.get(list.size() - 1).add("0.1");
    list.get(list.size() - 1).add("0.2");
    list.add(new ArrayList<String>());
    list.get(list.size() - 1).add("1.0");
    list.get(list.size() - 1).add("1.1");
    list.get(list.size() - 1).add("1.2");
    list.get(list.size() - 1).add("1.3");
    list.add(new ArrayList<String>());
    list.get(list.size() - 1).add("2.0");
    list.get(list.size() - 1).add("2.1");

    final String[][] array = ListConvert.convertNestedList(list);

    // @formatter:off
    final String[][] expected = new String[][] {
            { "0.0", "0.1", "0.2" },
            { "1.0", "1.1", "1.2", "1.3" },
            { "2.0", "2.1" } };
    // @formatter:on
    assertArrayEquals(expected, array);
}

It helps detecting regressions.


TypeScript JSON-Array Validator For my latest app I wanted to be able to code the front-end first, without having to do super extensive documentation and without forgetting my data types later on while coding the back-end.
I thus tried to make some kind of JSON Validator that expects something and outputs true or false depending on the input fed to it. (Meaning that I can define my data structures that way)

What I have works, but I'm not sure if that was the right way to go. Any comments?

export class ArrayValidator {

/**
 * Array-Template Syntax:
 * {
 *      "layer_type": "object"|"array"|"value",
        (if array):
        "items": -1,
        "item": {"layer_type": ...}
        (end if array)
        (if value)
        "value": 'regexp'
        (end if value)
        (if object)
        "properties": [
            {
                "name": "string",
                "null_allowed": true|false,
                "value": {"layer_type": etc ...}
            },
            {...}
        ]
        (end if object)
 *  }
**/
public static testUpon(arrayToTest, arrayTemplate) : boolean {
    if(arrayTemplate.layer_type == "object"){
        for(let prop of arrayTemplate.properties){
            if(arrayToTest[prop.name] == null && prop.nullAllowed == 'false'){
                console.log("[ArrayValidator][Error]Nonexistent property: " + prop.name);
                return false;
            }
            if(arrayToTest[prop.name] != null && !ArrayValidator.testUpon(arrayToTest[prop.name], prop.value)) return false;
        }
    }else if(arrayTemplate.layer_type == "array"){
        if(arrayTemplate.items!=-1 && arrayToTest.length != arrayTemplate.items){
            console.log("[ArrayValidator][Error]Array of wrong length.");
            return false;
        }
        for(let item of arrayToTest){
            if(!ArrayValidator.testUpon(item, arrayTemplate.item)) return false;
        }
    }else if(arrayTemplate.layer_type == "value"){
        let regexp = new RegExp(arrayTemplate.value);
        let res = regexp.test(arrayToTest);
        if(!res) console.log("[ArrayValidator][Error]Value Regexp doesn't match. [Regexp: " + arrayTemplate.value + ", Value: " + arrayToTest + "]");
        return res;
    }
    return true;
}

public static test(){
    let template = JSON.parse('{"layer_type": "object", "properties": [{"name": "obj", "nullAllowed": "false", "value": {"layer_type": "object", "properties": []}}, {"name": "embed", "nullAllowed": "false", "value": {"layer_type": "array", "items": -1, "item":{"layer_type": "value", "value": "(.+?)"}}}, {"name": "testVal", "nullAllowed": "false", "value": {"layer_type": "value", "value": "^[A-Za-z]+$"}}]}');
    let test = JSON.parse('{"testVal": "Hello", "embed": ["test", "another test", 24], "obj": {}}');
    console.log("Output: " + ArrayValidator.testUpon(test, template));
}
}

In other words, you're trying to validate that the parsed JSON matches the data structure you're expecting :)

I recommend creating a JSON Schema, updating it as you develop your front-end, and using a Schema Validator library to validate that the object you're creating is consistent with the schema.

This way, the schema will serve both as API documentation and as your test.


x86 FASM assembly Reverse FizzBuzz This program counts down from 100 to 1 and:

If the current number is a multiple of 3 it prints "Fizz" instead of the number
If it is a multiple of 5 it prints "Buzz" instead of the number
If it is a multiple of 3 and 5 it prints "FizzBuzz" instead of the number

format PE console
entry main

include 'macro/import32.inc'

section '.rdata' data readable
msg db '%d',13,10, 0
fizz db 'Fizz', 13, 10, 0
buzz db 'Buzz', 13, 10, 0
p db 'pause>nul', 0
fizzbuzz db 'FizzBuzz', 13, 10, 0
section '.data' data readable writeable
vdiv_by_3 dd 0
vdiv_by_5 dd 0

main:
push ebp
mov ebp, esp

mov ecx, 100

load_3:
mov eax, ecx
mov ebx, 3
xor edx, edx
div ebx
mov ebx, edx
mov [vdiv_by_3], ebx ; Store the remainder in div_by_3

load_5: ; Now check if its divisible by 5
mov eax, ecx
mov ebx, 5
xor edx, edx
div ebx
mov [vdiv_by_5], edx ; Remainder in div_by_5

cmp edx, 0 ; Checking 5
jne check_3_not_5

check_3:
mov eax, [vdiv_by_3]
cmp eax, 0
je print_fizzbuzz

check_3_not_5:
mov eax, [vdiv_by_3]
cmp eax, 0
je print_fizz

check_5_not_3:
mov eax, [vdiv_by_5]
cmp eax, 0
je print_buzz

print_num: ; Problem: This is printing 101 first, we need to start at 1
push ecx
push msg
call [printf] ; This call will mess with ecx so we have to store it
add esp, 4
pop ecx ; Get the counter back into ecx
jmp endme

print_fizz:
push ecx
push fizz
call [printf]
add esp, 4
pop ecx
jmp endme

print_buzz:
push ecx
push buzz
call [printf]
add esp, 4
pop ecx
jmp endme

print_fizzbuzz:
push ecx
push fizzbuzz
call [printf]
add esp, 4
pop ecx
jmp endme

print_number:
push ecx
push msg
call [printf]
add esp, 4
pop ecx

endme:
dec ecx
cmp ecx, 0
jne load_3
push p
call [system]
add esp, 4
push 0
call [exit]

section '.idata' import data readable
library msvcrt, 'msvcrt.dll'
import msvcrt, \
printf, 'printf', \
system, 'system', \
exit, 'exit'

Since you are writing FizzBuzz in assembler, you are obviously concerned about performance and code size.

For performance, div is one of the worst instructions. Since the divisibility repeats modulo 15, you could define some constants:

const divisible_by_3 = 0b1001001001001001
const divisible_by_5 = 0b1000010000100001

To test the divisibility, have an extra register that is initialized with i mod 15 and adjusted whenever i changes. The basic idea is:

dec i
dec i_mod_15
cmovs i_mod_15, 14   ; the maximum value mod 15

You can also combine divisible_by_3 and divisible_by_5 into a bit vector of two-bit entries (divisible) and define a jump table based on that. To do the actual testing, use bit-shifting.

const divisible_by_3 = 0b_1_0_0_1_0_0_1_0_0_1_0_0_1_0_0_1
const divisible_by_5 = 0b1_0_0_0_0_1_0_0_0_0_1_0_0_0_0_1_
const divisible      = 0b11000001001001000001100001000011

Another idea is to use unroll the loop by using Duff's Device.

Right now, your code is a really boring, straight-forward translation of some higher-level language, probably C. In assembler, you have much more potential to compress the code (DRY principle). For example, you can jmp do_printf instead of writing push ecx; call printf; pop ecx several times.

… 90 minutes later …

Based on the above ideas, the code might look like this, tested and works.

format PE console
entry main

include 'macro/import32.inc'

section '.rdata' data readable

; Each of these messages takes exactly 8 bytes,
; except for the last one.
; This is important for addressing them efficiently.
messages db '%d', 13, 10, 0, 0, 0, 0
         db 'Fizz', 13, 10, 0, 0
         db 'Buzz', 13, 10, 0, 0
         db 'FizzBuzz', 13, 10, 0

; This bit mask selects one of the above messages
; to be printed. The counter is always passed to
; printf, and in 8/15 cases it is ignored.
; The uu entry at the end is unused.
;
;                0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
; div3 mask =    1  0  0  1  0  0  1  0  0  1  0  0  1  0  0  u
; div5 mask =   1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  u
div_mask =      11_00_00_01_00_10_01_00_00_01_10_00_01_00_00_00b

section '.text' code readable

main:
        push ebp
        mov ebp, esp

        mov ecx, 100            ; ecx = the counter
        mov eax, ecx
        xor edx, edx
        mov ebx, 15
        div ebx                 ; edx = counter mod 15

        mov ebx, div_mask       ; ebx = bit mask for selecting the message
        rol ebx, 2
        xchg edx, ecx           ; Variable-width rotation is only possible
        rol ebx, cl             ; with cl, therefore the temporary swap
        rol ebx, cl             ; of edx and ecx.
        xchg edx, ecx           ;

.again:
        mov eax, ebx            ; Select the message format for printf.
        and eax, 11b
        shl eax, 3
        add eax, messages

        push ebx                ; save registers before printf
        push ecx
        push edx

        push ecx                ; actually call printf
        push eax
        call [printf]
        add esp, 8

        pop edx                 ; restore registers after printf
        pop ecx
        pop ebx

        dec edx                 ; Adjust counter, counter mod 15
        jns .normal             ; and bit mask.
        add edx, 15
        ror ebx, 2              ; Rotate one extra time since
.normal:                        ; the bit mask has 16 entries.
        ror ebx, 2

        dec ecx
        jnz .again

        xor eax, eax
        pop ebp
        ret

section '.idata' import data readable

library msvcrt, 'msvcrt.dll'

import msvcrt, printf, 'printf', system, 'system'

Some more things I took care of:

The code must not be in a writeable section.
Since the program can return from main, it should do so. To make that work, I had to add the pop ebp that corresponds to the push ebp at the very top; in your code that was missing.
I carefully avoided many branching statements, since they are poisonous to performance. See Why is it faster to process a sorted array.
The one remaining conditional behaves well in that it follows the jump in 14/15 cases, which is easily predictable.
Of course, using printf and the C stdio for output ruins all performance effects. But that's outside the scope for this little fun experiment.
All arguments to printf may be modified by printf. There's no guarantee that you get your ecx back at the point where you commented ; Get the counter back into ecx. To hide the counter from printf, you must push it once more to the stack. That's why I explicitly commented on this saving/calling/restoring in my code.

A nice thing is that you can play with the bit mask, which feels just like an ordinary configuration file.


Dungeon generation in Scala I've recently begun learning Scala, and while I've run into its concepts before (immutability, tuples, first-class functions) I'm not sure whether I'm using the language how it's supposed to be used. My learning project is going to be a simple little dungeon crawler, and while you can see the code on GitHub, I'm copying a simplified version here below.

Example output looks like this, where ?s are potential rooms and #s are actual rooms:

     ?
 ??  #  ?
?## ### #
  ### ####?
  ?? ## #
      ##
      #
    ?##?
     ??

And here's how it's implemented:

class LevelBuilder(random: Random) {

  /** Mapping of positions to the rooms at them. */
  var rooms: mutable.Map[(Int, Int), Room] = mutable.Map()

  /** List of areas where rooms could be generated. */
  var possibilities: Seq[(Int, Int)] = List()

  /**
   * Adds a new room to the map at the given position, and adds the available
   * positions around it to the possibilities list.
   */
  def addRoom(position: (Int, Int), room: Room): LevelBuilder = {
    rooms += position -> room

    // First, remove the room from the list of possibilities.
    possibilities = possibilities.filter(pos => pos != position).++(around(position))

    // Next, add the positions around that one to the list...
    possibilities = possibilities ++ around(position)

    // ...but then remove all of the ones around *those*, so no two paths will ever link up.
    possibilities = possibilities.filter(pos => roomPossibility(around(pos).count(p => rooms.contains(p))) && !rooms.contains(pos))

    this
  }

  /**
   * Determine whether a room should be build based on its number of neighbours.
   */
  private def roomPossibility(neighboursCount: Int): Boolean = {
    neighboursCount <= 1
  }

  /** Adds the given number of rooms to the level. */
  def addRooms(number: Int): LevelBuilder = {
    for (i <- 0 to number) {
      var index = random.nextInt(possibilities.length)        // Pick a random room from the possibilites list...
      addRoom(possibilities(index), Room.randomRoom(random))  // ...and add it
    }

    this
  }

  /** Return the four positions around the given one. */
  def around(position: (Int, Int)): Seq[(Int, Int)] = {
    List(
      (position._1 + 1, position._2),
      (position._1 - 1, position._2),
      (position._1, position._2 - 1),
      (position._1, position._2 + 1)
    )
  }

  /** Return a build layout of this level. */
  def build(): mutable.Map[(Int, Int), Room] = rooms.clone()

  /**
   * Print out a grid view of the level so far, showing both possibilities and
   * created rooms.
   */
  def debug() {
    val miny: Int = rooms.minBy(_._1._2)._1._2 min possibilities.minBy(_._2)._2  // there's got to be a better way to write this
    val maxy: Int = rooms.maxBy(_._1._2)._1._2 max possibilities.maxBy(_._2)._2
    val minx: Int = rooms.minBy(_._1._1)._1._1 min possibilities.minBy(_._1)._1
    val maxx: Int = rooms.maxBy(_._1._1)._1._1 max possibilities.maxBy(_._1)._1

    for (j <- miny to maxy) {
      for (i <- minx to maxx) {
        if (possibilities.contains((i, j))) {
          print("?")
        }
        else if (rooms.contains((i, j))) {
          print("#")
        }
        else {
          print(" ")
        }
      }
      println("")
    }
  }
}

So what do you all think? I've only been using Scala for a few days, so I'm interested to learn things like whether I should prefer using operators to methods, or whether there's a certain style of variable names I should be using, or anything like that.

Looking quickly over your code here are a couple of the changes I would make:

First, I would add a class to your application (probably within the levelbuilder.scala file) that encapsulates the (Int, Int) tuple you are using throughout this code snippet. E.g.

    case class Pos(x: Int, y: Int) {
      def neighborhood: List[Pos] = {
        Pos(x + 1, y) :: Pos(x - 1, y) :: Pos(x, y - 1) :: Pos(x, y + 1) :: Nil
      }
    }

When building this class I also took the chance to rewrite the method called around(pos: (Int, Int)) from the LevelBuilder class to a more concise method which I've called neighborhood just to differentiate it.

Also, if you haven't had a chance to read-up on case classes in Scala, now would be a good time to do so :) They provide a lot of functionality with just a few lines of code.

Now you may declare the LevelBuilder fields rooms and possibilities like so:

    val rooms = scala.collection.mutable.HashMap[Pos, Room]()
    var possibilities = List[Pos]()

One place that these changes drastically add to readability in your code is in the debug() method:

    def debug(): Unit = {
      val possibilePos = rooms.keys ++ possibilities

      val minY = possiblePos.minBy(_.y).y
      val maxY = possiblePos.maxBy(_.y).y
      val minX = possiblePos.maxBy(_.x).x
      val maxX = possiblePos.maxBy(_.x).x

      // print map
    }

Notice also that I changed miny to minY etc.


Formatting time delta Quite often, I find myself measuring how long some part of my code takes to complete. I normally do that by storing current time using time.time() and then subtracting time after the code is done.

This normally gives me a float that I can then format and print for debugging purposes. This is the function that I have for time formatting:

def time_format(delta: float) -> str:
    output = []
    decimal, integer = math.modf(delta)

    if integer:
        minutes, seconds = divmod(int(integer), 60)

        if minutes:
            output.append("%sm" % minutes)

        if seconds:
            output.append("%ss" % seconds)

    decimal, integer = math.modf(decimal * 1000)
    if integer:
        output.append("%sms" % int(integer))

    decimal, integer = math.modf(decimal * 1000)
    if integer:
        output.append("%sμs" % int(integer))

    decimal, integer = math.modf(decimal * 1000)
    if integer:
        output.append("%sns" % int(integer))

    return ", ".join(output)

I have also been told that the time module has most precision when it comes to time measuring so that's why I'm using it, instead of something like datetime which has nice formatting tools built in.

How could I improve my time formatting function? Are there any built in formatting tools that I'm not aware of? (Searching stack overflow leads me only to questions about datetime.timedelta)

There is indeed a function for that.

>>> from datetime import timedelta
>>> print(timedelta(seconds=1239.123456))
0:20:39.123456

Now, if I understand you correctly, you want a divider for the millisecond.

from datetime import timedelta
def f(secs):
    t=str(timedelta(seconds=secs))
    index = t.find('.') + 4
    return t[:index] + ' ' + t[index:]
print(f(1239.123456))
# 0:20:39.123 456

I don't like that everything is hardcoded, if you want to use it for different applications (or even languages), you might want to generalize your bases and names.

Here is a generic way of doing any formatting you want:

def prod(f):
    total = 1
    l = [1]
    for i in range(len(f)-1, 0, -1):
        total *= f[i][0]
        l.append(total)
    return reversed(l)

def format_time(number, f=((24, ':'), (60, ':'), (60, '.'), (1000, ' '), (1000, ''))):
    return ''.join(
        (f"{(number//div)%base:0>{len(str(base-1))}}" + delimiter)
        if number//div else ''
        for div, (base, delimiter) in zip(prod(f), f)
    )

formatting = (
    (24, ' hours '),
    (60, ' minutes '),
    (60, ' seconds '),
    (1000, ' milliseconds '),
    (1000, ' nanoseconds'),
)

print(
    format_time(1551198373998173),
    format_time(1551198373998173, formatting),
    format_time(1551739, formatting),
    sep="\n"
)

The result is:

16:26:13.998 173
16 hours 26 minutes 13 seconds 998 milliseconds 173 nanoseconds
01 seconds 551 milliseconds 739 nanoseconds

What are it's advantages, you can do any formatting in any base, with any names. We could even do a base 2 converter.

binary_formatting = (((2, ' '),)+((2, ''),)*3)*10 + ((2, ''),)

print(
    format_time(155933900, binary_formatting),
    format_time(3279, binary_formatting),
    sep="\n"
)

1001 0100 1011 0101 1100 1100 1100
1100 1100 1111

Other than that, if your code need to accomplish a single purpose and it does it well, good for you.


Linux: Raku script to open files from terminal and ask for deletion Raku script to open files from terminal with xdg-open and, with del option, asks for deletion. Happy to receive Raku syntax improvements. Thanks!
use v6;

#| Linux: Opens file 'pattern.ext' with xdg-open and, with del option, asks for deletion
sub MAIN( $pattern is copy, Str $ext, Str $del? where ( $del ∈ < del nodel > ) = "nodel" ) {

    $pattern = "" if $pattern eq "all";
    my @files = '.'.IO.dir(test => /.*$pattern.*\.$ext/);

    for @files -> $file {
        my @args = 'xdg-open', $file.basename;
        my $command = run @args;
        $command.exitcode == 0 or die "system @args failed: $!";
        if $del eq 'del' {
          my $delete = prompt("\n \n Delete file $file (s/n) ");
          next if $delete ne "s";
          say "mv $file /tmp/$file";
          $file.IO.move("/tmp/$file");
        }
        my $exit = prompt("\n Press 'q' to end, return to continue ");
        last if $exit eq q{q};
    }

    @files = '.'.IO.dir(test => /.*$pattern.*$ext$/);
    say "-" x 60;
    for @files -> $file { $file.Str.say }
    say "-" x 60;
}

If I just run your program without any arguments, this is what I get:
Usage:
  foo.raku <pattern> <ext> [<del>] -- Linux: Opens file 'pattern.ext' with xdg-open and, with del option, asks for deletion

That's not super helfpul, so let's tackle that first.
#| Linux: Opens file 'pattern.ext' with xdg-open and, with del option, asks for deletion
sub MAIN(
    $pattern is copy, #= The pattern to match against (use 'all' to match everything)
    Str $ext, #= The extension for the file
    Str $del? where ( $del ∈ < del nodel > ) #= Options for opening ('del' or 'nodel', defaults to 'nodel')
        = "nodel"
) {
   ...
}

This produces much nicer output:
Usage:
  foo.raku <pattern> <ext> [<del>] -- Linux: Opens file 'pattern.ext' with xdg-open and, with del option, asks for deletion

    <pattern>    The pattern to match against (use 'all' to match everything)
    <ext>        The extension for the file
    [<del>]      Options for opening ('del' or 'nodel', defaults to 'nodel')

One thing you'll note is that the #= syntax doesn't play nicely with default values, so while I normally prefer using #= for parameters, the #| might be better when you have defaults.  I personally like to let it breathe a bit more when doing this, but YMMV.
#| Linux: Opens file 'pattern.ext' with xdg-open and, with del option, asks for deletion
sub MAIN(

    #| The pattern to match against (use 'all' to match everything)
    $pattern,

    #| The extension for the file
    Str $ext,

    #| Options for opening ('del' or 'nodel', defaults to 'nodel')
    Str $del? where {$del <del nodel>} = "nodel"
) {
    ...
}

You'll notice I adjust the $del where clause a bit.  Where clauses expect a block, and using parentheses like you did along with the default value can cause problems IME where the equals sign gets gobbled into the block implied block, so explicit blocks are safest.  Because you've set a default value, you don't need to mark it as explicitly optional.
Now let's look at your main code.  First we have the line
my @files = '.'.IO.dir(test => /.*$pattern.*\.$ext/);

First, instead of '.'.IO, you can use $*CWD, which identifies the purpose a bit better.  Your regex pattern is a bit off also.  Let's comment it and you'll see what's going on:
    my @files = $*CWD.dir:
        test => /
            .*        # match any characters
            $pattern  # then the pattern
            .*        # then any characters
            \.        # then literal period
            $ext      # then the extension
        /);

Regexen declared with / / aren't anchored to the start or end, so the initial .* isn't necessary.  OTOH, you will want an explicit end so you can do
    my @files = '.'.IO.dir:
        test => /
            $pattern  # the pattern
            .*        # then any characters
            \.        # then literal period
            $ext      # then the extension
            $         # and end the filename
        /);

It might add a few lines to your code, but commenting regex is a very good idea and can help you catch bugs sometimes.
Now in your main logic block
    for @files -> $file {
        my @args = 'xdg-open', $file.basename;
        my $command = run @args;
        $command.exitcode == 0 or die "system @args failed: $!";
        if $del eq 'del' {
          my $delete = prompt("\n \n Delete file $file (s/n) ");
          next if $delete ne "s";
          say "mv $file /tmp/$file";
          $file.IO.move("/tmp/$file");
        }
        my $exit = prompt("\n Press 'q' to end, return to continue ");
        last if $exit eq q{q};
    }

Separating out your arguments for run into a separate variable is nice, although obviously not strictly necessary.  Because the result of run is truthy based on its success, and we don't use the exit code anywhere else, we can just put the run inside the unless clause.  If that's compacting too much into too small of a space for you, or if you'll need to use the exit code for later expansions of the script, you could use my $command = run @args; fail '...' unless $command.  (ht Brad in comments).
One thing to consider is if you really want to die.  I don't know the xdg-open command personally, so not sure its mechanics.  If you do need to die (terminates the entire script), then by all means do so.  But since each file is being handled separately, perhaps you'd prefer to warn the user and continue with the others.  In that case, you could use a fail, optionally with a CATCH handler to provide more detailed support:
    for @files -> $file {
        my @args = 'xdg-open', $file.basename;

        fail "system @args failed: $!"
            unless run @args;

        if $del eq 'del' {
            my $delete = prompt("\n \n Delete file $file (s/n) ");
            next if $delete ne "s";
            say "mv $file /tmp/$file";
            $file.IO.move("/tmp/$file");
        }

        my $exit = prompt("\n Press 'q' to end, return to continue ");
        last if $exit eq 'q';

        CATCH {
           .message.say;
           next if prompt "Would you like to continue processing other files?" eq "y";
           exit 0;
        }
    }

You'll notice I also gave it a little bit of extra space.  Think of it like separating paragraphs in your code.  I would recommend against using q{q} to match q, just use 'q'.  The special quote structures have their place, but this doesn't feel like one of them.
For the final bit of code, the same thing I mentioned about the regex will apply.  For the output:
    say "-" x 60;
    for @files -> $file { $file.Str.say }
    say "-" x 60;

Works well, but the middle line can be greatly simplified to .Str.say for @files.


Searching an object tree structure I have this recursive function that searches an object tree structure:

dataSearcher = (dataElement, identifierToFind) ->
    if dataElement.identifier == identifierToFind
        return dataElement
    else
        for childDataElement in dataElement.children
            found = dataSearcher childDataElement, identifierToFind
            if found then return found

Which I then call thus:

foundDataElement = dataSearcher @options.nodeData, identifier

It works just fine so I am happy about that, but I am pretty new to CoffeeScript and would like feedback on the way I structured it.  The loop I used seems a bit old school, so could I have used a comprehension here instead?  Any other feedback would be great as I am still getting my head into the CoffeeScript idiom.

Please let me know if I should edit with more context code.

I'd prefer writing it like this:

dataSearcher = (element, identifier) ->
  return element if element.identifier is identifier
  for child in element.children
    found = dataSearcher child, identifier
    return found if found

Changes:

guard style instead of else (one less level of indentation)
postfix if (probably a question of style)
is instead of ==
shorter variable names


Forking with PHP (4 different approaches) I thought about three (now four) different ways how to execute forks with PHP.
What is the faster, maybe better solution and why?

PHP script included

foreach($tasks as $task) {
    $pid = pcntl_fork();

    if($pid == -1) {
            exit("Error forking...\n");
    } else if($pid == 0) {

            include 'worker.php';
            exit();

    }
}

while(pcntl_waitpid(0, $status) != -1);`

PHP script executed through exec()

foreach($tasks as $task) {
    $pid = pcntl_fork();

    if($pid == -1) {
            exit("Error forking...\n");
    } else if($pid == 0) {

            exec('php worker.php '.$task);
            exit();

    }
}

while(pcntl_waitpid(0, $status) != -1);

PHP script executed as background command

foreach($tasks as $task) {

    $workers[] = exec('php worker.php '.$task.' &  echo $!');

}

do {
    foreach($workers as $idx => $pid) {
            if(!posix_getpgid($pid)) {
                    unset($workers[$idx]);
            }
    }
} while(!empty($workers));

(additional) 4. Using Gearman

worker.php can open database connections, files, etc ...

Any good explanation would be much appreciated.

5. All code embedded in a single PHP script. With explanation as requested.

The statements before the fork is executed normally.

After a succesful pcntl_fork(), the running process is cloned, complete with its current state (all variables, including process counter). So two identical processes continue from that point in code.
Almost identical: the only difference is the return values of pcntl_fork(), stored in both $pid's.

The cloned process is the parent, and receives the process_id of its clone.
The clone process is the child, and receives 0.
Depending on this value, both processes go their separate ways, and continue until the hit an exit().
If parent- and child-code are not individually terminated by exit(), then both may continue executing the common code at the end, resulting both processes printing "I am both"!.
Try for yourself, and inspect the output. Then uncomment the exit()'s and run it again.

$mypid = getmypid();
echo "$mypid: I am the parent. I have no child yet.\n";

// fork: a twin process is created
if(($pid = pcntl_fork()) == -1) { exit("Error forking...\n"); }

if($pid == 0) {
        // Child code goes here
        $mypid = getmypid();
        echo "$mypid: I am the child. This is what I do.\n";
        // exit();
}else{
        // Parent code goes here
        echo "$mypid: I am still the parent. I have a child now: it's number is $pid.\n";
        // exit();
}

// Both parent and child execute this code unless
// the exit's above are uncommented.
echo "$mypid: we are both. The pid I know is: $pid\n";

exit();

Output: of the script above. The $mypid at the beginning of the line is the process id of the printing process. The $pid on the right is the return-value of the fcntl_fork().

6346: I am the parent. I have no child yet.
6347: I am the child. This is what I do.
6346: I am still the parent. I have a child now: it's number is 6347.
6346: we are both. The pid I know is: 6347
6347: we are both. The pid I know is: 0

Note: after the fcntl_fork() both processes work independently. So one may go faster than the other; they may run on different processes, etc.
The order of the output may differ on your computer !
You can have them synchronized by making the parent wait for the childs exit.

This was my attempt to give an explanation. Now the answer to your question, wich one is faster or better:

Essentially they are all the same, as far as the fork goes. The differences are only in th extras.

An include makes the 'compiler' translate the code all at once. And only once.
All variables set in the main program (before the fork ! ) are 'inherited' by the child.

An exec cleans all process variables and starts a new program, just as you do from the command line. So this is overhead. And no information is shared from the parent to the child. (unless you  ... well, there are possibilities).
A new process in a clean memory also forces the child code to be compiled in the second process. So the compiler has to be started again; this to is overhead.

So without exec is always better ? No. For example: if your co-worker changes his child-code, his typo's will make the compiler stop compiling your code if is is included.
But executing the other code will clearly show where the typo's are made. Programs are insulated much better this way. At some cost. Depends on how often you want the fork to be executed.


Outputting Errors to User I currently am making a small application where a user will enter their ID which needs to be in a certain format.  When entered in the wrong format, different output errors are produced.

I currently output errors like this:

public void errorLogger(string error)
        {
            errors += error + Environment.NewLine + "
";
        }

I have read that using += is not a great operator to use. Alternatively I have thought this may be better:

public void errorLogger(string key, string err)
        {
            if(!String.IsNullOrEmpty(err))
            output.Add(key, err);
        }

but then I basically do the same thing later:

    string keys = "";
    foreach (KeyValuePair<string, string> entry in core.errorLogger())
    {
        keys += entry.Key + ":       " + entry.Value + "
";
    }

Is there a cleaner way to output errors?  The output is injected under the submit button into:

errorSpan.InnerHtml = (keys);

This is what I ended up using going off of Charles' response to AWinkle

public void logError(string err, string desc)
                {
                    if(!String.IsNullOrEmpty(desc))
                        errors.AppendFormat("{0,10}:&nbsp;{1}
", err, desc);
                }
public string getErrors()
            {
                return errors.ToString();
            }

Then :

errorspan.InnerHtml = (core.getErrors());

Using the StringBuilder class will typically be better for looped string building.

string keys = "";
foreach (KeyValuePair<string, string> entry in core.errorLogger())
{
    keys += entry.Key + ":       " + entry.Value + "
";
}

turns into

StringBuilder keys = new StringBuilder();
foreach (KeyValuePair<string, string> entry in core.errorLogger())
{
    keys.AppendFormat("{0}:&nbsp;{1}
", entry.Key, entry.Value);
}

Then you take errorSpan.InnerHtml = (keys); and change it to errorSpan.InnerHtml = (keys.ToString());

Alternatively, you could use this to replace the dictionary as CharlesNRice suggests.

StringBuilder keys = new StringBuilder();

 public void errorLogger(string key, string err)
    {
        if(!String.IsNullOrEmpty(err))
        keys.AppendFormat("{0}:&nbsp;{1}
", key,err);
    }


Find lexicographical permutations I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm.

The basic layout of my problem is as follows:
I have a string that is composed of only H's and V's. There can be not more than 10 H's and 10 V's possible. I need to find the Kth lexicographical order of such pattern. Also, inp[] array contains input is format:

2 2 3
4 5 4

which means that total H = 2, total V = 2 and I need to print 3rd lexicographical permutation of HHVV.
Similarly for 4 5 4, I need to print 4th lexicographical permutation of HHHHVVVVV.

//This function returns the next lexicographical permutation of the StringBuilder s
static StringBuilder getKRankString(StringBuilder s)
{
    char ch[] = (s.toString()).toCharArray();
    int i = 0, j=0;
    //This loop gets the highest i for which ch[i]<ch[i+1]
    for(int k=0;k<s.length()-2;k++){
        if(ch[s.length()-2-k]<ch[s.length()-1-k]){
            i = s.length()-2-k;
            break;
        }

    }
    //System.out.println(i);
    //This loop gets the highest j for which ch[j]>ch[i]
    for(int k=s.length()-1;k>i;k--){
        if(ch[k]>ch[i]){
            j = k;
            break;
        }

    }
    //System.out.println(j);
    //swap characters at i and j
    char temp = ch[i];
    ch[i] = ch[j];
    ch[j] = temp;
    //Append the original string till i to reversed string from i till end
    StringBuilder swapped = new StringBuilder(new String(ch));
    //System.out.println(swapped);
    String sb1 = swapped.substring(0, i+1);
    String sb2 = (new StringBuilder(swapped.substring(i+1, s.length())).reverse()).toString();
    StringBuilder str = new StringBuilder(sb1+sb2);
    return str;
}

static String[] gridLand(String[] inp) {
    String[] outputArr = new String[inp.length];
    for(int i=0;i<inp.length;i++){
    //get the first line of input and get integer x and y
        int x = Integer.valueOf(inp[i].split(" ")[0]);
        int y = Integer.valueOf(inp[i].split(" ")[1]);
        int k = Integer.valueOf(inp[i].split(" ")[2]);
        StringBuilder sb = new StringBuilder();
    //form the original string using x H's and y V's.
    //This will be the first String of this order
        for(int j = 0; j < x; j++)
            sb = sb.append("H");
        for(int j = 0; j < y; j++)
            sb = sb.append("V");
        //String s1 = sb.toString();
    //run the below functoin K times to get Kth lexicographical string
        for(int m = 0; m < k; m++)
            sb = getKRankString(sb);
        outputArr[i] = sb.toString();
    }
    return outputArr;

}

Encoding

I hope I understood the problem correctly :)

When observing the problem, I found you can replace the H and V with 0 and 1. The lexicographical permutations then become binary numbers. There are only 10 V's and 10 H's, so the final number will be below 2^20 so fits even in an int.

   HHHVV -> 00011
   VVHHH -> 11000
   etc.

Start out by setting the starting int to  (1 << Vs) -1 and use the next-bit permutation logic from here

Then, if you found the nth permutation, transform it back to a String

Time complexity

As calculation the next bit permutation is simply a constant time calculation, finding the nth permutation takes O(n) time.

Proposed solution

public class Permutations
{
    //treat H as 0, V as 1.
    private static String getLongAsHVString( long size, long l )
    {
        String s = Long.toBinaryString( l ).chars().mapToObj( Permutations::getStr ).collect( Collectors.joining() );

        //Prepend the 'missing' zeroes as 'H' s
        while ( s.length() < size )
        {
            s = "H" + s;
        }
        return s;
    }

    private static String getStr( int c )
    {
        return ( c == '0' ) ? "H" : "V";
    }

    private static long getNthLexoPerm( int hCount, int vCount, int n )
    {
        long current = ( 1 << vCount ) - 1;

        for ( int i = 0; i < n; i++ )
        {
            current = nextPerm( current );
        }
        return current;
    }

    private static String getNthLexoPermAsString( int hCount, int vCount, int n )
    {
        return getLongAsHVString( hCount + vCount, getNthLexoPerm( hCount, vCount, n ) );

    }

    public static long nextPerm( long v )
    {
        long t = ( v | ( v - 1 ) ) + 1;
        return t | ( ( ( ( t & -t ) / ( v & -v ) ) >> 1 ) - 1 );

    }

    public static void main( String[] args )
    {

        System.out.println( getNthLexoPermAsString( 2, 2, 3 ) );
        System.out.println( getNthLexoPermAsString( 4, 5, 4 ) );
    }

}


Checking whether a word satisfies a template with wildcards I'm working one of the recommended tutorials -- actually, the UPenn online course CS194 -- for learning Haskell, and I have a working solution to the final "challenge exercise" for HW 2. But it seems to be a very brute-force way of doing things, so I'm wondering if this is really the idiomatic Haskell way, or if I'm bringing my imperative programming habits in by accident.

The function is supposed to take a template representing a portion of a Scrabble board, and a set of tiles making up the Scrabble "hand", and see if you can legally play a given word within those constraints. The input would be:

A Template - a string containing letters or '?' characters, representing empty spaces
A Hand - a list of characters representing the available letters that can fill in the spaces.
A Word - the string being checked to see if it fits the template.

A word "fits" the template if:

Every letter in the template matches the letter at that position in the word
Every '?' in the template can be replaced by the letter at that position in the word by removing it from the hand
'?' letters at the end of the template can also be "blank", if the template is longer than the word.

e.g.:

wordFitsTemplate "??r?" [’c’,’x’,’e’,’a’,’b’,’c’,’l’] "care" == True
wordFitsTemplate "??r?" [’c’,’x’,’e’,’w’,’b’,’c’,’l’] "care" == False
wordFitsTemplate "??r?" [’c’,’x’,’e’,’a’,’b’,’c’,’l’] "car" == True
wordFitsTemplate "let" [’x’,’x’] "let" == True

This is what I came up with; I feel like there are too many different patterns and guards that I should be able to condense somehow:

type Hand = [Char]
type Template = String

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate [] _ []            = True
wordFitsTemplate [] _ _             = False
wordFitsTemplate _ [] _             = False
wordFitsTemplate (t:ts) h []
    | t == '?'                      = wordFitsTemplate ts h []
    | otherwise                     = False
wordFitsTemplate ('?':ts) hs (s:ss)
    | s `elem` hs                   = wordFitsTemplate ts (delete s hs) ss
    | otherwise                     = False
wordFitsTemplate (t:ts) hs (s:ss)
    | t == s                        = wordFitsTemplate ts hs ss
    | otherwise                     = False

Let's omit the first 3 conditions (for now).

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate (t:ts) hs []
    | t == '?'                      = wordFitsTemplate ts hs []
    | otherwise                     = False
wordFitsTemplate ('?':ts) hs (s:ss)
    | s `elem` hs                   = wordFitsTemplate ts (delete s hs) ss
    | otherwise                     = False
wordFitsTemplate (t:ts) hs (s:ss)
    | t == s                        = wordFitsTemplate ts hs ss
    | otherwise                     = False

First, we can see that if we have an empty array, we're going to just check if the rest of the string is full of question marks. Let's reduce that case first. (This gives us the additional benefit of covering the case where we are given an empty template and string)

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate ts hs [] = all (== '?') ts
wordFitsTemplate ('?':ts) hs (s:ss)
    | s `elem` hs                   = wordFitsTemplate ts (delete s hs) ss
    | otherwise                     = False
wordFitsTemplate (t:ts) hs (s:ss)
    | t == s                        = wordFitsTemplate ts hs ss
    | otherwise                     = False

This is sort of messy, so let's introduce a helper function which checks a char from the template and the string. It returns a boolean indicating if it matches and the hand.

charFitsTemplate :: Char -> Hand -> Char -> (Bool, Hand)
charFitsTemplate t hand c
    | t == '?' && c `elem` hand = (True, delete c hand)
    | otherwise = (t == c, hand)

Let's redefine our wordFitsTemplate function now.

wordFitsTemplate :: Template -> Hand -> String -> Bool
wordFitsTemplate ts _ [] = all (== '?') ts
wordFitsTemplate (t:ts) hand (c:cs) = isFit && wordFitsTemplate ts newHand cs
    where (isFit, newHand) = charFitsTemplate hand t c
wordFitsTemplate _ _ _ = False

It should be noted that when isFit evaluates to False, the function returns False; otherwise, when it evaluates to True, the result of the function depends on wordFitsTemplate ts newHand. Hence, we can combine them using &&.

This is the closest I could get to a nice solution. :) In functional programming, it's best to think of how to compartmentalize the problem and make it more elegant. In this case, we seperated the checking of whether a character matches (as well as the hand handling, no pun intended) with checking the template string. This gives us a rather elegant solution.


Java getters and setters Below is the code I would like some help with.  I'm just trying to understand if there a better way to use getters and setters.  Can someone fill me in on the correct way to use them if there is a textfield, JRadioButton set that I am trying to get info from?

//This class sets gets all the information that the user has entered.
package edu.witc.TrainTicket.model;

import java.text.NumberFormat;

import javax.swing.JOptionPane;
import javax.swing.JRadioButton;
import javax.swing.JTextField;

import edu.witc.TrainTicket.view.*;

public class Destination {

    //Constructor with no arguments
    public Destination() {
    }

    public Destination(JRadioButton chicago, JRadioButton newYork, JRadioButton seattle, JRadioButton sanFransisco, JTextField name, JTextField phone) {

        String selectedDestination = getRadioButtonValue(chicago, newYork, seattle, sanFransisco);
        String custName = getCustName(name);
        String custPhone = getPhoneNum(phone);

        }

    public String getCustName(JTextField name){
        return name.getText();
    }

    public String getPhoneNum(JTextField phone){
        return phone.getText();
    }

    //get the type of paint
    public String getRadioButtonValue(JRadioButton chicago, JRadioButton newYork, JRadioButton seattle, JRadioButton sanFransisco) {

        String selected = "";

        if(chicago.isSelected())
            selected = "Chicago";
        if(newYork.isSelected())
            selected = "New York";
        if(seattle.isSelected())
            selected=  "Seattle";
        if(sanFransisco.isSelected())
            selected=  "San Fransisco";

        //JOptionPane.showMessageDialog(null, selected);

        return selected;
    }
}

Your getters and setters would be for fields of the class, not passed in.  I'll use your two simplest ones as examples for you to work from.

public String getCustName(JTextField name){
    return name.getText();
}

public String getPhoneNum(JTextField phone){
    return phone.getText();
}

These methods make no sense if you think about them logically.  Your client code will pass in a JTextField that it already has, in order to invoke getText() on it?  Why wouldn't that code just do it itself?

Here's how getters and setters work:

private JTextField myTextField;

public String getMyTextFieldValue() {
    return myTextField.getText();
}

public void setMyTextField(JTextField newTextField) {
    myTextField = newTextField;
}

That's the general principle behind getters and setters.  You should be able to extend that logic to all of the other methods as well once you understand the logic.


Displaying markers for local attractions on a Google map I have created a page that displays markers for local attractions on a Google map.  There are a few functions that do similar tasks and I have tried to reduce these by incorporating them into one function, but to no avail. Any suggestions on how to go about doing this?

First off, I find it helpful to use arrays instead of multiple variables. So, how about this:

var map = [], infoWindow = [];

Then, lets rename id map to map0. This will allow us to be clever with how we reference it :)

Now we refactor initialize to use the array and reduce repetition:

function initialize(){
   initMap(0, 51.5069999695, -0.142489999533);
   initMap(1, 40.79445,-74.01558);
   initMap(2 , 48.858001709, 2.29460000992);
}

function initMap(ndx, lat, lng){
   var feed = new google.maps.LatLng(lat, lng);

   map[ndx] = new google.maps.Map(document.getElementById('map'+ndx), {
      mapTypeId: google.maps.MapTypeId.ROADMAP,
      center: feed,
      zoom: 11
   });

   var request = {
      location: feed,
      radius: 5000
   };

   infoWindow[ndx] = new google.maps.InfoWindow();
   var service = new google.maps.places.PlacesService(map);
   service.search(request, callback);
}

Finally, lets refactor createMarker to use the arrays as well.

function callback(results, status) {
   if (status == google.maps.places.PlacesServiceStatus.OK) {
      for (var i = 0; i < results.length; i++) {
         createMarker(0, results[i]);
         createMarker(1, results[i]);
         createMarker(2, results[i]);
      }
   }
}

function createMarker(ndx, place) {
   var marker = new google.maps.Marker({
      animation: google.maps.Animation.DROP,
      map: map[ndx],
      position: place.geometry.location
   });

   google.maps.event.addListener(marker, 'click', function() {
      infowindow[ndx].setContent(place.name);
      infowindow[ndx].open(map[ndx], this);
   });
}

google.maps.event.addDomListener(window, 'load', initialize);

Finally, don't forget to rename map to map0


TicTacToe game in C# I have been studying C#, and I am trying to model the Tic Tac Toe game. Is my program reasonable or is there anything I need to improve?

 enum Result
{
    None,
    Win,
    Draw
}

public class TicTacToe
{
    static char[] board = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    char player = 'O';
    Result result = Result.None;

    public void PlayGame()
    {
        Intro();
        do
        {
            Console.Clear();
            Console.WriteLine("Player 1 : O Player 2 : X");
            DrawBoard();
            Console.WriteLine($"\nPlayer {player}'s Turn \nPlease Enter the empty number");

            label:
            int choice = 0;

            while (!int.TryParse(Console.ReadLine(), out choice))
            {
                Console.WriteLine("Enter the num please");
            }
            if (choice >= 10)
            {
                Console.WriteLine("Please enter btw 1 - 9");
                goto label;
            }

            if (board[choice] != 'X' && board[choice] != 'O')
            {
                board[choice] = player;
                ChangeTurn();
            }

            CheckWin();
        } while (result != Result.Draw && result != Result.Win);

        Console.Clear();
        DrawBoard();
        GameResult();
        Console.ReadKey();

    }

    void ChangeTurn()
    {
      if (player == 'X')
          player = 'O';
      else if (player == 'O')
          player = 'X';
    }
    void GameResult()
    {
        if (result == Result.Win)
        {
            ChangeTurn();
            Console.WriteLine("Player {0} has won", player);
        }
        else if(result == Result.Draw)
        {
            Console.WriteLine("Draw");
        }
        Console.ReadLine();
    }
    void Intro()
    {
        Console.WriteLine("Welcome to TieTacToe");
        Console.WriteLine("Press any Key to continue");
        Console.ReadKey();
        Console.Clear();
    }
    void DrawBoard()
    {
        int x = 1;
        Console.WriteLine();
        for (int row = 0; row < 3; row++)
        {
            Console.Write("| ");
            for (int col = 0; col < 3; col++)
            {
                Console.Write(board[x]);
                Console.Write(" | ");
                x++;
            }
            Console.WriteLine();
        }
    }
    void CheckWin()
    {
        // horzontial
        if (board[1] == board[2] && board[2] == board[3])
        {
            result = Result.Win;
        }
        else if (board[4] == board[5] && board[5] == board[6])
        {
            result = Result.Win;
        }
        else if (board[7] == board[8] && board[8] == board[9])
        {
            result = Result.Win;
        }
        // vertical
        else if (board[1] == board[4] && board[4] == board[7])
        {
            result = Result.Win;
        }
        else if (board[2] == board[5] && board[5] == board[8])
        {
            result = Result.Win;
        }
        else if (board[3] == board[6] && board[6] == board[9])
        {
            result = Result.Win;
        }
        // X
        else if (board[1] == board[5] && board[5] == board[9])
        {
            result = Result.Win;
        }
        else if (board[3] == board[5] && board[5] == board[7])
        {
            result = Result.Win;
        }
        else if (board[1] != '1' && board[2] != '2' && board[3] != '3' && board[4] != '4' && board[5] != '5' && board[6] != '6' && board[7] != '7' && board[8] != '8' && board[9] != '9')
        {
            result = Result.Draw;
        }
        else
        {
            result = Result.None;
        }
    }
}

If you want to be completely safe, I would also check the 'choice' to make sure that it was not a negative number.

Goto's should be avoided. You can easily refactor your code to use a while loop and break.

In your function GameResult(), I would use a switch statement instead of the if chain.

I am also thinking that CheckWin() might be a bit too cumbersome with all of the if statements and the checking of the individual cells. I might keep a "shadow board" behind the scenes, where a cell is 1 if it is an X and -1 if it is an O. Some simple addition and a test to see if the Math.Abs(sum) == 3 is an easy way to test for a win. For example:

if (Math.Abs(board[1] + board[2] + board[3]) == 3)
  result = Result.Win;

You can even refactor what I wrote above by keeping a list of the triplets to check.

Good luck with your studies of C#.


XML/HTML batch generator As part of an exercise I've written some code to generate multiple HTML files based on information stored in a couple of XML files. I'm not really sure how much code you'd need to evaluate my function so this is most of the relevant code regarding the actual HTML from XML generation:

  # search taxonomy.xml for nodes with the attribute 'atlas_node_id'
  # to get a NodeSet of all the destinations
  destinations = tax_file.css('[atlas_node_id]')

  # cd to directory you want to create the files in
  FileUtils.cd(directory)

  destinations.each do |destination|
    # temp variable to make code easier to read later on
    id = destination.attribute('atlas_node_id').value

    html = Nokogiri::HTML::Builder.new do |doc|
      doc.html{
        doc.head{
          doc.title destination.children[1].content
          doc.link(rel: 'stylesheet', href: "all.css")
        }

        doc.body{
          doc.h1{
            doc.text destination.children[1].content
          }

          # check if there is a destination higher in the taxonomy and display
          # the relevant link if so.
          if !(destination.parent.attribute('atlas_node_id').nil?)
            file = destination.parent.children[1].content + ".html"
            doc.a(:href => file){
              doc.text destination.parent.children[1].content
            }
          end

          # I chose to show the overview content since this exists for every
          # destination
          doc.p{
            node = dest_file.xpath("//destination[@atlas_id = #{id}]").first
            doc.text node.xpath(".//introductory/introduction/overview").text unless
            node.nil?
          }
        }
      }
    end

    # write file using destination name as filename
    filename = destination.children[1].content + ".html"
    directory << File.open(filename,'w').write(html.to_html)
  end

At the moment the XML files in questions are small (there are only 24 destinations in total) so everything works without problems. How can I refactor this to make if more performant for situations where there are many thousands of destinations?

If your problem is speed and the generated HTML is as easy as it look in your example code, then I would not use the Nokogiri Builder.

Take a HTML-Template and build your files according this template.

Example (without an example XML I was not able to check it):

# search taxonomy.xml for nodes with the attribute 'atlas_node_id'
# to get a NodeSet of all the destinations
destinations = tax_file.css('[atlas_node_id]')

destinations.each do |destination|
# temp variable to make code easier to read later on
id = destination.attribute('atlas_node_id').value

# write file using destination name as filename
filename = destination.children[1].content + ".html"
File.open(File.join(directory,filename),'w'){|html|
  html << <<HTML % destination.children[1].content
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">

<title>%s</title>
<link rel='stylesheet' href="all.css">

HTML
  html << "
%s
\n" % destination.children[1].content

      # check if there is a destination higher in the taxonomy and display
      # the relevant link if so.
      if !(destination.parent.attribute('atlas_node_id').nil?)
        file = destination.parent.children[1].content + ".html"
        html << '%s' % [file,destination.parent.children[1].content]
        html << "\n"
      end

      # I chose to show the overview content since this exists for every
      # destination
      node = dest_file.xpath("//destination[@atlas_id = #{id}]").first
      html << "
%s
\n" % node.xpath(".//introductory/introduction/overview").text unless node.nil?
      html << ""
  }

end


Using a template to cycle through a sequence of containers I'm trying to implement a template that takes a container as parameter. The template has a getnext method that cycles through the elements in the parameter. Take note that I'm not using C++11.

Header:

#pragma once

template<template<class, class> class TContainer, class TObject>
class cycle
{
public:

    explicit cycle( TContainer<TObject, std::allocator<TObject>> & container )
        : mContainer( container ), index(0) {}

    TObject getNext(int numObjectsToCycle)
    { return mContainer[index++ % numObjectsToCycle]; }
private:
    TContainer<TObject, std::allocator<TObject>> & mContainer;
    int index;
};

Implementation:

#include <iostream>
#include <vector>

#include "cycle.h"

using namespace std;

class Processor
{
   int mIndex;
   vector<int> numbers;

public:
   cycle<vector, int> cycler;
   // Is it safe to pass numbers since it is declared first??
   Processor() : mIndex(0), cycler(numbers) {}
   void update() { cout << numbers[mIndex++ % numbers.size()] << std::endl;}
   void addNumber(int x) { numbers.push_back(x); }
};

int main()
{
   Processor S;

   for (int i = 0; i < 5; ++i)
   {
      S.addNumber(i+1);
   }
   cout << "using update" << endl;
   for (int c = 0; c < 10; ++c)
   {
      S.update();
   }

   cout << "using cycle" << endl;
   for (int c = 0; c < 10; ++c)
   {
      cout << S.cycler.getNext(5) << endl;
   }

   std::cin.get();

}

Any improvement or potential issues to the code?

Here is how I would write it:

template<typename C>
class cycle
{
    C& mContainer;
    size_t index;
    using ref = decltype(mContainer[0]);

public:
    explicit cycle(C& container) :
        mContainer(container), index(0) {}

    ref getNext()
    {
        return mContainer[index++ % mContainer.size()];
    }
};

Notes:

The template parameter is the container, C. This not only simplifies code, but also works for containers that do not follow a specific pattern, e.g. have more parameters than just a value type and an allocator type.
The return type of getNext is automatically inferred from C. This is not just C's value_type but a (non-const) reference to it.
If I understand correctly from the title, C is supposed to be a sequence of containers? If so, the value_type is a container itself so it is even more important that a reference is returned from getNext.
Why pass a parameter to getNext? To cycle correctly, you should use mContainer.size(), exactly as you do in Processor::update, right?
index is of type size_t

With only a few changes, here is Processor:

class Processor
{
   size_t mIndex;
   std::vector<int> numbers;

public:
   cycle<std::vector<int>> cycler;
   Processor() : mIndex(0), numbers(), cycler(numbers) {}
   void update() { std::cout << numbers[mIndex++ % numbers.size()] << std::endl;}
   void addNumber(int x) { numbers.push_back(x); }
};

Notes:

again, mIndex is a size_t
cycler is a cycle<std::vector<int>>
numbers is default-initialized
cycler is safely constructed after numbers

Also, whenever you want to

using namespace std;

for convenience, only do it inside another (your own) namespace, never globally.

EDIT

I just noticed you're not using C++11. In this case, just use

    typedef typename C::value_type& ref;

instead.


return array element if it exists, otherwise null Given is an array $array and a key $key.  If the array has the key, then I want to return the value, otherwise null. Is there a better way in PHP7 now, then doing it like that:

return (empty($array[$key])) ? null : $array[$key];

For the question title, there indeed a null coalescing operator introduced in PHP7:

return $array[$key] ?? null;

which is a shorthand for

return (isset($array[$key])) ? $array[$key] : null;

however, in your code you are using empty() which is different from isset() and for this code there is no shorthand in PHP.

with empty(), your code will also return null if $array[$key] exists but contains an empty-like value, like false, 0, empty array and such


Defining a DataTemplateBase I have defined some DataTemplates are similar. The templates are like this:

    <DataTemplate x:Key="DefaultCellTemplate">
    <TextBlock Text="{Binding Value}">
        <i:Interaction.Behaviors>
            <beh:AddErrorButtonAdornerToControlsBehavior
                DoOnButtonClick="{Binding RelativeSource={RelativeSource AncestorType={x:Type dxg:GridControl}}, Path=DataContext.ShowErrorDialogCommand}"
                FieldDescriptionId="{Binding RelativeSource={RelativeSource Mode=FindAncestor, AncestorType={x:Type dxg:GridCellContentPresenter}}, Path=Column.Tag}"/>
        </i:Interaction.Behaviors>
    </TextBlock>
</DataTemplate>

<DataTemplate x:Key="TimeCellTemplate">
    <TextBlock Text="{Binding Value, Converter={StaticResource TimeConverter}}">
        <i:Interaction.Behaviors>
            <beh:AddErrorButtonAdornerToControlsBehavior
                DoOnButtonClick="{Binding RelativeSource={RelativeSource AncestorType={x:Type dxg:GridControl}}, Path=DataContext.ShowErrorDialogCommand}"
                FieldDescriptionId="{Binding RelativeSource={RelativeSource Mode=FindAncestor, AncestorType={x:Type dxg:GridCellContentPresenter}}, Path=Column.Tag}"/>
        </i:Interaction.Behaviors>
    </TextBlock>
</DataTemplate>

<DataTemplate x:Key="StationCellTemplate">
    <TextBlock Text="{Binding Value, Converter={StaticResource StationConverter}}">
        <i:Interaction.Behaviors>
            <beh:AddErrorButtonAdornerToControlsBehavior
                DoOnButtonClick="{Binding RelativeSource={RelativeSource AncestorType={x:Type dxg:GridControl}}, Path=DataContext.ShowErrorDialogCommand}"
                FieldDescriptionId="{Binding RelativeSource={RelativeSource Mode=FindAncestor, AncestorType={x:Type dxg:GridCellContentPresenter}}, Path=Column.Tag}"/>
        </i:Interaction.Behaviors>
    </TextBlock>
</DataTemplate>

<DataTemplate x:Key="ProductionCategoryCellTemplate">
    <TextBlock Text="{Binding Value, Converter={StaticResource ProductionCategoryConverter}}">
        <i:Interaction.Behaviors>
            <beh:AddErrorButtonAdornerToControlsBehavior
                DoOnButtonClick="{Binding RelativeSource={RelativeSource AncestorType={x:Type dxg:GridControl}}, Path=DataContext.ShowErrorDialogCommand}"
                FieldDescriptionId="{Binding RelativeSource={RelativeSource Mode=FindAncestor, AncestorType={x:Type dxg:GridCellContentPresenter}}, Path=Column.Tag}"/>
        </i:Interaction.Behaviors>
    </TextBlock>
</DataTemplate>

I don't know, if I can define a template base. The template base should be a TextBlock with the behavior and the derived templates should be use a converter for the TextBlock value. Any idea?

Real inheritance is not possible in DataTemplate through XAML, as far as I know. What you can do with is use a nested construction of DataTemplates.

The method boils down to using a ContentPresenter and setting the ContentTemplate property in order to achieve your nesting.

Solutions are already presented on SO and Google; both give a good bit of information:

Stack Overflow
Stack Overflow
Google


Safely pruning merged topic branches locally Background

My team develops in a git monorepo. User stories are broken into very small discrete sub-tasks and merged directly into master, rather than into a feature branch for the story.

Topic branches

Our topic branch names are all of the form issue/<developer username>/<subtask ticket>.

Those are pushed to origin and merged via a code-reviewed pull-request process.

Release branches

We also maintain long-lived release branches named release/sprint/<number> used for hot-patching.

Release branches are never re-merged to master. The individual fixes, if relevant in the current release, are re-implemented in another branch or applied as a patch. There are few enough of them to manage manually.

Work

This works well for us, but it means we have hundreds of topic branches hanging around as developers often forget to delete them as they go.

I wrote a simple bash script to

Sync up with origin (we have only one),
Figure out which branches have been merged into master (or, optionally, a different branch, so far nobody has used that),
Delete locally-merged branches,
Optionally run the gc

The verbose prompting at every stage is intentional as reassurance.

Concerns

Primarily, is this "safe", meaning:

Have I used an appropriate method to list branches?
Have I used an appropriate method for deleting branches?
Have I accounted for all possible pathways that could result in destruction of a local branch?
Have I adequately guarded against destruction of a local branch not merged into master?
Should I verify that topic branches have been merged into origin's master and not the local master, in the event that a user mistakenly merges locally and loses their branch?

I'm very happy for any additional comments, no matter how nit-picky.

Code

#!/bin/bash
MERGED_INTO=${1:-"master"}

statistics() {
  echo
  echo "Remaining local branches:"
  git branch

  echo
  echo "These local branches are not merged into ${MERGED_INTO}:"
  git branch --no-merged ${MERGED_INTO}

  echo
  echo "Size of local repo: $(git count-objects)"

  git status
}

error () {
  echo "WARNING: Something went wrong. Aborting..."
  if [[ ${1} ]]; then echo "The previous command exited with ${?}"; fi

  echo "This is the current state of your working copy:"
  git status
}

confirm () {
  read -r -p "Are you sure? [y/N] " response
  case ${response} in
    [yY][eE][sS]|[yY])
      true
      ;;
    *)
     echo "Ok, aborting..."
     echo
     false
     ;;
  esac
}

check_on_main_branch() {
  local current_branch;
  current_branch=$(git symbolic-ref -q --short HEAD)
  if [ "${current_branch}" != "${MERGED_INTO}" ]; then
    echo "You should be on '${MERGED_INTO}' for this operation. I can switch branches for you."
    confirm && git checkout "${MERGED_INTO}" || error $?
  fi
}

delete_local_merged_branches() {
  git branch --merged ${MERGED_INTO} | egrep -v "(^\*|${MERGED_INTO})" | xargs git branch --delete
}

# Step 1
echo "Fetching remote branch state"
git fetch --all

# Step 2
echo "The following local branches have been merged into ${MERGED_INTO} and will be deleted locally:"
git branch --merged ${MERGED_INTO} | egrep -v "(^\*|${MERGED_INTO})"
confirm && delete_local_merged_branches

# Step 3
echo "Would you like to run the garbage collector?"
confirm && \
 echo "Before garbage collecting: $(git count-objects)" && \
 git gc

trap statistics EXIT
trap error SIGHUP SIGINT SIGTERM

The final line has no effect:

trap error SIGHUP SIGINT SIGTERM

As the program is about to exit, we're exceedingly unlikely to receive any of those signals between this point and the end of the program.

It's much more usual to set the trap handler as soon as you've defined the error function.

Similarly, the exit trap

trap statistics EXIT

is the same as simply

statistics

when we're about to exit.  I suggest that this line is moved to before Step 1, too.


HackerRank - Almost Sorted I've written the following algorithm to solve this HackerRank problem using STL algorithms.

Problem statement

  Given an array with n elements, can you sort this array in ascending
  order using only one of the following operations?

  Swap two elements.
  Reverse one sub-segment.

  Input Format

  The first line contains a single integer, n, which indicates the size
  of the array.   The next line contains  integers separated by spaces.

n
d1 d2 ... dn

  Output Format

  If the array is already sorted, output yes on the first line. You do not need to output anything else.
  If you can sort this array using one single operation (from the two permitted operations) then output yes on the first line and then:

  If you can sort the array by swapping d_l and d_r, output "swap l
  r" in the second line. l and r are the indices of the elements to be
  swapped, assuming that the array is indexed from 1 to n.
  Else if it is possible to sort the array by reversing the segment
  d[l...r], output "reverse l r" in the second line. l and r are the
  indices of the first and last elements of the subsequence to be
  reversed, assuming that the array is indexed from 1 to n.

  d[l...r] represents the sub-sequence of the array, beginning at index
  l and ending at index r, both inclusive.

  If an array can be sorted by either swapping or reversing, stick to
  the swap-based method.

  If you cannot sort the array in either of the above ways, output "no" in the first line.

Code

#include <vector>
#include <iostream>
#include <algorithm>

int main() {
    int n; std::cin >> n;
    std::vector<int> v;
    v.reserve(n);
    while(n--){
        int x; std::cin >> x;
        v.push_back(x);
    }
    auto v_sorted = v;
    std::sort(v_sorted.begin(),v_sorted.end());

    auto mismatch_1 = std::mismatch(v.begin(),v.end(),
                                    v_sorted.begin());
    auto mismatch_2 = std::mismatch(std::next(mismatch_1.first),v.end(),
                                    std::next(mismatch_1.second));
    auto mismatch_3 = std::mismatch(v.rbegin(),v.rend(),
                                    v_sorted.rbegin());

    if (std::prev(mismatch_3.first.base()) == mismatch_2.first) {
        if (*std::prev(mismatch_2.first)<=*mismatch_1.first) {
           std::cout
               << "yes\n" << "swap "
               << std::distance(v.begin(),mismatch_1.first) + 1
               << " "
               << std::distance(v.begin(),mismatch_2.first) + 1;
        }
    }
    else {
       std::reverse(mismatch_1.first,mismatch_3.first.base());
       if (std::equal(mismatch_1.first,std::prev(mismatch_3.first.base()),mismatch_1.second)) {
           std::cout
               << "yes\n" << "reverse "
               << std::distance(v.begin(),mismatch_1.first) + 1
               << " "
               << std::distance(v.begin(),std::prev(mismatch_3.first.base())) + 1;
       }
       else {
           std::cout << "no";
       }
    }

    return 0;
}

Questions

My main question is about reverse iterators. I feel it's a little bit confusing when I compare them with forward iterators, as I need to do std::prev(reverse_iterator.base()). Do you think this affects readability or is the code fine like it is? Any other suggestion?

I find the reverse iterators a bit confusing, but I might be a little slow. That said, I'm probably not the only one, so you wouldn't waste your time looking for a simpler way to express yourself.

I'd add that you forgot to handle the case where the input is already sorted, meaning that you could have been overwhelmed yourself ;-)

My suggestion, using std::adjacent_find to detect sign changes (note that I use a reverse iterator only once, to denote the vector's last element -in that case it feels intuitive to me):

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

void is_almost_sorted(std::vector<int>& vec) {
    // find swap candidates, swap and check if sorted
    auto first  = std::adjacent_find(vec.begin(), vec.end(), std::greater<int>()); // first sign change...
    if (first == vec.end()) {
        std::cout << "Already sorted";
        return;
    }
    auto bkp = vec;
    auto second = std::adjacent_find(first+1, vec.end(), std::greater<int>()); // and second
    if (second != vec.end()
        && (std::iter_swap(first, second+1), std::is_sorted(vec.begin(), vec.end()))) {
        std::cout << "swap " << *first << " and " << *++second;
        return;
    }
    // restore from original vec
    auto offset = std::distance(vec.begin(), first);
    vec = std::move(bkp);
    first = vec.begin()+offset;
    // find inverse change of signs, reverse and check if sorted
    second = std::adjacent_find(first+1, vec.end(), std::less<int>());
    std::reverse(first, second == vec.end() ? second : second + 1);
    if (std::is_sorted(vec.begin(), vec.end())) {
        std::cout << "reverse from " << *first
                  << " to " << (second == vec.end() ? *std::rbegin(vec) : *++second);
        return;
    }
    std::cout << "no solution";
}


Counting subsets with sum not exceeding some limit I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the following DP relations

#number of ways to get sum using subsets of {1, 2, ..., i}
dp[i][sum] += dp[i - 1][sum]            #not using element i
dp[i][sum + array[i]] += dp[i - 1][sum] #using element i

Constraints:

1 <= n <= 30
1 <= array[i] <= 1e9
0 <= limit <= 1e9
Time: 1s
Memory: 64 Mb

At first I considered using plain array( or std::array, whatever) but an array dp[30][1e9 + 1] can't be allocated on stack and heap allocation would be too expensive given time limit of 1 second. I came up with the following implementation using std::unordered_map:

std::unordered_map<int, int> dp;

for (int element_idx = 0; element_idx < i_size; ++element_idx) {

  if (arr[element_idx] > limit) {
    continue;
  }
  std::unordered_map<int, int> new_sums;
  new_sums[arr[element_idx]] = 1;
  if (!element_idx) {
    dp = std::move(new_sums);
    continue;
  }
  for (std::pair<int, int> &sum_count : dp) {
    new_sums[sum_count.first] += sum_count.second;
  }

  for (std::pair<int, int> &sum_count : dp) {
    if (sum_count.first + arr[element_idx] <= limit) {
      new_sums[sum_count.first + arr[element_idx]] += sum_count.second;
    }
  }
  dp = std::move(new_sums);
}

The problem it that this implementation runs into a memory limit error. Moreover, my computer just freezes if the input is 30 distinct 6-, 7-digit integers. I am pretty sure there is nothing wrong with my algorithm and the only problem my poor algorithm implementation experience and C++ knowledge.

The problem is actually with your algorithm, not with your C++ code. The time complexity of your solution is \$O(2^n \times \text{polynomial}(n))\$, which is too much for the given constraints.

You can use the meet-in-the-middle technique to make it \$O(2^{(n/2)} \times \text{polynomial}(n))\$, which is good enough.

The idea is as follows:

Let's split the array into two even parts (almost even if n is odd).
Let's generate all sums in the first in and in the second part and store them in vectors as and bs. This part requires \$O(2^{(n/2)})\$.
Now the problem is simpler: given two vectors A and B, compute the number of pairs of valid indices i and j such that as[i] + bs[j] <= S for a given value of S.
Let's sort bs and iterate over as. As bs is increasing, all valid elements of bs for a given element a from as are in some prefix of B. We can find its size as std::upper_bound(bs.begin(), bs.end(), a) - bs.begin()
That is, this part of this solution looks like:

for (const auto& a : as) {
    result += std::upper_bound(bs.begin(), bs.end(), a) - bs.begin();
}

The total time complexity is \$O(2^{(n/2)} \times \log(2^{(n/2)}) = O(2^{(n/2)} \times n)\$.


Breadth First Search to find connected primes I've been working through the British Informatic Olympiad's 2016 Paper, and I've been struggling with some of the larger cases for question 3, specifically the larger cases on the mark scheme (the 3 before last specifically).

  Two prime numbers are connected if the difference between them is 2n for some whole number n ≥ 0.
  A path is a sequence of (at least two) prime numbers, without repetition, where adjacent numbers in the sequence are connected. If
  the first number in the sequence is p and the last number is q
  then we say the path is between p and q.
  The length of a path is the total number of prime numbers used. There may be multiple paths between two prime numbers; the lengths of
  these paths may be different.

  Write a program to determine the length of the shortest path between
  two primes. Your program should accept three integers in order: l (4
  ≤ l ≤ 224) indicating the highest value you are allowed to use,
  followed by the primes p then q (2 ≤ p < q < l). You will only
  be given input where there is a path between p and q using values
  below l. You should output the length of the shortest path.

Inputs I was struggling with:

614700 3643 90149 | outputs 18
987654 3643 90149 | outputs 16
1000000 2 968137  | outputs 18

How can I improve its performance?

import math

primes = None
upper_limit = 0
powers_of_two = []

class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent
    def get_adjacent(self):
        for i in powers_of_two:
            if (self.value + i < upper_limit
            and self.parent != self.value + i
            and self.value + i in primes):
                yield Node(i+self.value, self)
            if (self.value - i >= 2
            and self.parent != self.value - i
            and self.value - i in primes):
                yield Node(self.value - i, self)

def sieve(n):
    numbers = list(range(0, n))
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break
        for i in range(prime ** 2, n, prime):
            numbers[i] = 0
    return [x for x in numbers if x > 1]

def bfs(f, to):
    f = Node(f, None)
    q = [f]
    visited = [f.value]
    while len(q) != 0:
        if q[0].value == to:
            return q[0]
        else:
            for x in q[0].get_adjacent():
                #print(q[0].value, x.value)
                if x.value not in visited:
                    #print("added", x.value)
                    visited.append(x.value)
                    q.append(x)
        del q[0]
while True:
    inp = [int(x) for x in input().split(' ')]
    upper_limit = inp[0]
    m = int(math.ceil(math.log2(inp[0]))) if math.log2(inp[0]) % 1 != 0 else int(math.log2(inp[0]))
    for i in range(0, m):
                   powers_of_two.append(2**i)
    primes = sieve(inp[0])
    x = bfs(inp[1], inp[2])
    counter = 0
    while x is not None:
        print(x.value)
        x = x.parent
        counter += 1

    print("--------------------")
    print(counter)

There are 3 major performance problems you currently have:

the primes is currently a list and every time you do something in primes - this is O(n) average-time complexity (where n is the length of primes) - define primes as a set instead
the visited is a list, same O(n) lookups - define it as a set instead
the del q[0] is also a O(n) operation - removing an element from the beginning of a list requires rearranging all following elements - use a collections.deque in place of a list for O(1) deletes from both ends (.popleft() for the left-end deletion)

Revised version (works for me in an instant for all the test inputs):

import math
from collections import deque

class Node:
    __slots__ = ['value', 'parent']

    def __init__(self, value, parent):
        self.value = value
        self.parent = parent

    def get_adjacent(self, primes):
        for i in powers_of_two:
            if self.value + i < upper_limit and self.parent != self.value + i and self.value + i in primes:
                yield Node(i + self.value, self)
            if self.value - i >= 2 and self.parent != self.value - i and self.value - i in primes:
                yield Node(self.value - i, self)

def sieve(n):
    numbers = list(range(0, n))
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break

        for i in range(prime ** 2, n, prime):
            numbers[i] = 0

    return {x for x in numbers if x > 1}

def bfs(f, to, primes):
    f = Node(f, None)

    q = deque([f])
    visited = set([f.value])
    while q:
        if q[0].value == to:
            return q[0]
        else:
            for x in q[0].get_adjacent(primes):
                # print(q[0].value, x.value)
                if x.value not in visited:
                    # print("added", x.value)
                    visited.add(x.value)
                    q.append(x)
        q.popleft()

if __name__ == '__main__':
    upper_limit, p, q = [int(x) for x in input().split(' ')]

    m = int(math.ceil(math.log2(upper_limit))) if math.log2(upper_limit) % 1 != 0 else int(math.log2(upper_limit))
    powers_of_two = [2 ** i for i in range(m)]

    primes = sieve(upper_limit)

    x = bfs(p, q, primes)

    counter = 0
    while x is not None:
        print(x.value)
        x = x.parent
        counter += 1

    print("--------------------")
    print(counter)

You can also see some other changes:

removed the while True loop (from what I understand you just need a single run)
using if __name__ == '__main__':
avoiding using globals and passing the primes set to the bfs() and get_adjacent() as an argument
using __slots__ for the Node class
used list unpacking for reading the input numbers
used upper_limit, p and q variables to increase readability (p and q variable names are used in the problem description)


Calculating minima values for each column of given data Can anyone help make this perform faster?

import numpy as np
from scipy import signal

d0 = np.random.random_integers(10, 12, (5,5))
d1 = np.random.random_integers(1, 3, (5,5))
d2 = np.random.random_integers(4, 6, (5,5))
d3 = np.random.random_integers(7, 9, (5,5))
d4 = np.random.random_integers(1, 3, (5,5))
d5 = np.random.random_integers(13, 15, (5,5))

data = np.array([d0,d1,d2,d3,d4,d5])  ####THIS SHAPE IS GIVEN, WHICH CAN NOT BE CHANGED.
data = data.reshape(6,25)

data = data.T
minimas=[]
for x in data:
    minima = signal.argrelmin(x, axis=0)
    minimas.append(x[minima])

print minimas    ####THIS SHAPE IS GIVEN, WHICH CAN NOT BE CHANGED.

Note: this only works if there are exactly two minima in each row.

You can avoid the loop by computing minima along axis 1 of the data array.

minima = signal.argrelmin(data, axis=1)
minimas = list(data[minima].reshape(-1,2))


Count number of ways that sequences contain at least one of the given subsequences Peter loves dices and some special numbers. Therefore he thrown dice n times and concatenate the numbers. Compute the probability that if he throws 6 to 27 seven times dice and concatenate the numbers, the sequence contains at least one subsequence of number sequence

1, 2, 3, 4, 5, 6
1, 1, 2, 2, 3, 3
4, 4, 5, 5, 6, 6
1, 1, 1, 2, 2, 2
3, 3, 3, 4, 4, 4
5, 5, 5, 6, 6, 6
1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2, 2
3, 3, 3, 3, 3, 3
4, 4, 4, 4, 4, 4
5, 5, 5, 5, 5, 5
6, 6, 6, 6, 6, 6

I saw that there is a way to do it by Markov chains. Is there any way to write the code more elegantly, like using inclusion-exclusion principle?

My code that uses Markov chains:

from sets import Set

def matMul(a,b):
    zip_b = zip(*b)
    return [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
             for col_b in zip_b] for row_a in a]

"""Matrix power for positive integer power"""
def matPow(a, n):
    if n<1: return None
    if n==1: return a

    if n%2==0:
        aToHalfN = matPow(a, n/2)
        return matMul(aToHalfN, aToHalfN)
    else:
        return matMul(matPow(a, n-1), a)

def getProbSomeSeqIsSub(symbols, seqs, n, exactRational=False):

    def cleanSeqs(arr):
        ret = list(arr)
        changed = True
        while changed:
            changed = False
            for x in ret:
                hadADelete = False
                for y in ret:
                    if x!=y and y in x:
                        ret.remove(x)
                        hadADelete = True
                        changed = True
                        break
                if hadADelete:
                    break
        return ret

    seqs = cleanSeqs(seqs)

    symbolsLen = len(symbols)
    prefixes = Set([""]) #first state is '' empty start state

    for seq in seqs:
        for i in xrange(1, len(seq)):
            prefixes.add(seq[0:i])

    prefixes = sorted(list(prefixes))
    M = len(prefixes)+1 #last state (index M-1) is the absorbing one

    def findFallsBackTo(appendedRun):
        for i in xrange(0,len(appendedRun)):
            if appendedRun[i:] in prefixes:
                return appendedRun[i:]
        return ""

    def incrState(stateDict, state):
        if state in stateDict:
            stateDict[state] += 1
        else:
            stateDict[state] = 1

    def someEndInSeqs(s):
        for i in xrange(len(s)):
            if s[i:] in seqs: return True
        return False

    def getToStateVals(stateStr):
        ret = {}
        for i in symbols:
            stPlusI = stateStr+str(i)
            if someEndInSeqs(stPlusI):
                incrState(ret, M-1)
            elif stPlusI in prefixes:
                incrState( ret, prefixes.index(stPlusI) )
            else:
                fallsToPrefix = findFallsBackTo(stPlusI)
                incrState(ret, prefixes.index(fallsToPrefix))
        return ret

    a = []
    aInts = []
    for i in xrange(M):
        a += [[]]
        aInts += [[]]
        for j in xrange(M):
            a[i] += [0]
            aInts[i] += [0]

    for i in xrange(M-1):
        ps = getToStateVals(prefixes[i])
        for toI in ps:
            a[toI][i] = float(ps[toI])/symbolsLen
            aInts[toI][i] = ps[toI]

    a[M-1][M-1] = 1.0
    aInts[M-1][M-1] = symbolsLen

    if exactRational: return str(matPow(aInts, n)[M-1][0])+" / "+str(symbolsLen**n)
    else: return matPow(a, n)[M-1][0]

for i in range(6,28):
 a = getProbSomeSeqIsSub([1,2,3,4,5,6], ["123456", "112233", "445566",  "111222", "333444", '555666', '111111', '222222', '333333', '444444',  '555555', '666666'], i, True)

 b = a.split("/")
 oso = int(b[0])
 nimi = int(b[1])
 print(str(i)+ " "+str(oso*6**i/nimi))

Use numpy!

Don't roll your own matMul. It's not worth it. numpy will outperform you and will be simpler to use. The same goes for matPow, though (I'm not sure) you may still need to write a thin wrapper around numpy.

Python names

Use snake_case for functions and variables, such as

get_sub_prob

Make a main function

...to pull your last six lines out of global scope.