Month: November 2014

Bandit Level 24 → Level 25

Level Goal

A daemon is listening on port 30002 and will give you the password for bandit25 if given the password for bandit24 and a secret numeric 4-digit pincode. There is no way to retrieve the pincode except by going through all of the 10000 combinaties, called brute-forcing.


Again, I created a folder inside /tmp and make sure both the newly created folder and all the file related to this level must have proper permission (chmod 755 would be enough).

#!/bin/bash
passwd="UoMYTrfrBFHyQXmg6gzctqAwOmw1IohZ"

for a in {0..9}{0..9}{0..9}{0..9}
do
    echo $passwd' '$a | nc localhost 30002 >> result &
done

I choose to use netcat (nc) but telnet works just as well. The passcode a is being generated by 4 brace expansions. The >> append the output to the file result. The & put the command in background so it can start the next iteration. Doing so save me a lot of time waiting for this script to be done. To improve upon this, I need to find a way to terminate the loop when the correct answer is displayed. However, I didn’t know what the correct message would be at the beginning.

Using the same strategy to find an unique line from Level 8 → Level 9, we see the password for the next level is the unique line of result file.

$ sort result | uniq -u
Correct!
The password of user bandit25 is uNG9O58gUE7snukf3bvZ0rxhtnjzSGzG

Additional References:

Advertisements

Problem 20

99 Haskell Problems

Problem 20

(*) Remove the K’th element from a list.

Example in Prolog:

?- remove_at(X,[a,b,c,d],2,R).
X = b
R = [a,c,d]

Example in Lisp:

* (remove-at '(a b c d) 2)
(A C D)

(Note that this only returns the residue list, while the Prolog version also returns the deleted element.)

Example in Haskell:

*Main> removeAt 2 "abcd"
('b',"acd")

Solution:

removeAt :: Int -> [a] -> (a, [a])
removeAt n (x:xs) 
    | n == 1 = (x, xs)
    | otherwise = (ys, x:zs)
        where (ys, zs) = removeAt (n-1) xs

This is similar to the solution from problem 17. we use the where clause to connect the missing link between ys, zs and xs.

Problem 19

99 Haskell Problems

Problem 19

(**) Rotate a list N places to the left.

Hint: Use the predefined functions length and (++).

Examples:

* (rotate '(a b c d e f g h) 3)
(D E F G H A B C)

* (rotate '(a b c d e f g h) -2)
(G H A B C D E F)

Examples in Haskell:

*Main> rotate ['a','b','c','d','e','f','g','h'] 3
"defghabc"
 
*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)
"ghabcdef"

Solution:

rotate :: [a] -> Int -> [a]
rotate [] _ = []
rotate xs 0 = xs
rotate (x:xs) n 
 | n > 0 = rotate (xs++[x]) (n-1)
 | otherwise = rotate (x:xs) (length (x:xs) + n)

The case n < 0 is represented in the otherwise by call rotate with a positive value.

Problem 18

99 Haskell Problems

Problem 18

(**) Extract a slice from a list.

Given two indices, i and k, the slice is the list containing the elements between the i’th and k’th element of the original list (both limits included). Start counting the elements with 1.

Example:

* (slice '(a b c d e f g h i k) 3 7)
(C D E F G)

Example in Haskell:

*Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7
"cdefg"

Solution:

slice :: [a] -> Int -> Int -> [a]
slice [] _ _ = []
slice (x:xs) a b
    | a > 1 && b > 0 = slice xs (a-1) (b-1)
    | b > 0 = x:(slice xs 0 (b-1))
    | otherwise = []

This was very similar to the previous problem. I used the input as an indices for counting what to extract out.

Problem 17

99 Haskell Problems

Problem 17

(*) Split a list into two parts; the length of the first part is given.

Do not use any predefined predicates.

Example:

* (split '(a b c d e f g h i k) 3)
( (A B C) (D E F G H I K))

Example in Haskell:

*Main> split "abcdefghik" 3
("abc", "defghik")

Solution:

split :: [a] -> Int -> ([a],[a])
split [] _ = ([], [])
split xs n = (fstPart xs n, sndPart xs n)

fstPart [] _ = []
fstPart (x:xs) n
 | n == 0 = []
 | otherwise = x:(fstPart xs (n-1))

sndPart [] _ = []
sndPart (x:xs) n
 | n == 0 = (x:xs)
 | otherwise = sndPart xs (n-1)

The fstPart basically does exactly what take does. The sndPart basically does exactly what drop does. Looking at the solution, we can use where to simplify this greatly:

split :: [a] -> Int -> ([a],[a])
split [] _ = ([], [])
split (x:xs) n
 | n > 0 = (x:ys, zs)
 | otherwise = ([], x:xs)
 where (ys, zs) = split xs (n-1)
The where clause in this case relates (ys, zs) to xs and eliminate the need to define them separately.

Chapter 9: Control I – Expression and Statements

  • An expression returns a value and produces no side effect (in pure mathematical form)
  • A statement is executed for its side effects and return no value.

9.1 Expression

  • If the evaluation of an expression causes no side effects, then the expression will yield the same result, regardless of the order of evaluation of its subexpression. In the presence of side effects, the order of evaluation can make a difference.
  • short-circuit evaluation evaluate left-to-right up to the point where the truth value of the entire expression becomes known and then the evaluation stops.
  • referential transparency (substitution rule) is any two expressions in a program that have the same value may be substituted for each other anywhere in the program. Their values always remain equal, regardless of the context in which they are evaluated.
  • normal order evaluation of an expression means that each operation (or function) begins its evaluation before its operands are evaluated, and each operand is evaluated only if it is needed for the calculation of the value of the operation.
  • normal order evaluation is lazy evaluation in Haskell and pass by name in Algo160.

9.2 Conditional Statements and Guards

  • If-Statements
    • {if (e1) if (e2) S1 else S2} has a dangling-else ambiguity where the last else could be associate with either the first or second else.
    • Solution: diambiguating rule or bracketing keyword
  • Case- and Switch-Statements

9.3 Loops and Variations on WHILE

  • for loop vs while loop
for (e1; e2; e3) S;

e1;
while (e2) {
  S;
  e3;
}

9.4 The GOTO Controversy and Loop Exits

  • structured vs unstructured loop exist
int search(int array[], int target){
  boolean found = false;
  int index = 0;
  while (index < array.length && ! found) 
    if (array[index] == target)
      found = true;
    else
      index++;
  if (found)
    return index;
  else
    return -1;
}

int search(int array[], int target){
  for (int index = 0; index < array.length; index++) 
    if (array(index) == target)
      return index;
  return -1;
}

9.5 Exception Handling

  •  explicit control mechanism has a syntactic indication of the transfer at the point where a transfer control takes place. The opposite is implicit transfer of control where there is no indication.
  • exception handling is the control of error conditions or other unusual events during the execution of a program. It involves the declaration of both exceptions and exception handlers.
  • exception is any unexpected or infrequent event
  • exception handler is a procedure or code sequence that is designed to be executed when a particular exception is raised and that is supposed to make it possible for normal execution to continue in some way.
  • asynchronous exceptions occur at any moment and not just in response to the execution of program code.
  • synchronous exceptions occur in direct response to actions by the program.
  • resumption model of exception handling return to the point at which the exception was first raised and begin execution again.
  • termination model of exception handling continue execution with the code immediately following the block or expression in which the handler that is executed was found.

9.6 Case Study: Computing the Values of Static Expressions in TinyAda

Additional Notes

Exercise

Other Resources

concurrent.futures: a simple multi-thread execution

Recently I was expose to a way to launch parallel tasks in python by using concurrent.futures.  Let say you have a function call doSomething(i) that do something with a value, i and return a result. You can setup a pool of 8 threads as following:

executor = concurrent.futures.ThreadPoolExecutor(max_workers=8)

If we need to doSomething(i) on a range(64) values, we can map the result using the executor as follow:

results = executor.map(doSomething, range(64))

This will return an array of 64 result. Be sure to signal the executor to free any resources by having the following line.

executor.shutdown()

Additional References: