Coding things

## Category: Puzzles

### Mazes (1)

As mentioned previously, I had an assignment which involved constructing a maze from code and letting a robot escape from it. This series won’t follow the second part, it will concentrate on maze specific topics. I will write about maze generation, maze drawing, maze counting and several other aspects. Maybe I’ll touch several properties of the mazes, possibly I’ll write about something like the moments in statistics. Will see where this series will end and what areas will be covered by it.

### Solving XKCD’s Nerd Sniping problem

A while ago, during a period of free time, I implemented a solution in Haskell for the XKCD’s raptor problem. Now, I’ll try to solve another problem presented there, the one found in the Nerd Sniping comic. Of course, the implementation will still be in Haskell.

### Raptors

All xkcd‘s fans know the raptor problem: suppose you are standing at the centre of an equilateral triangle with three raptors in the corners, one of them injured (thus going with a slower speed). Knowing the speeds of all entities and the edge of the triangle determine the direction in which you will have to run to maximize your life time.

### Ships

Let’s say we have two ships arranged on a line. Both ships are sailing with the same speed. However, while the first one is always going in a perpendicular direction to the line initially connecting the ships, the second one will always try to go towards the first.

We are asked to determine the distance between the ships after enough time has passed.

### Raytracing

Yet another puzzle solved in Haskell. This time we have a raytracing problem. A simplified version but, nonetheless, hard to do in a functional way. At least in a non-monadic fashion.

Enough talk. Let’s see the problem: suppose we have a box with size n by m. Inside the box we have some light sensors – some cells which are initially black and which will turn to another colour as soon as one light ray comes very close to them. The sensors are placed at all integer coordinates in the box (assuming that the maximum allowed coordinates are n and m). Their sensitivity is chosen such that a cell is active only if the ray passes the point where the sensor is placed. Filling the box with sensors, we would like to obtain a picture of their state after several light sources are placed in the box.

### Segmented Sieve Of Eratosthenes

Today’s Programming Praxis problem describes an algorithm which may be used to find the prime numbers in a large interval, so large that it cannot be kept in memory at once. See their description there, I’ll only give the code in Haskell.

First, some utility functions:

```firstQ :: Int -> Int -> Int firstQ l pk = (-(1+l+pk) `div` 2) `mod` pk   nextQ :: Int -> Int -> Int -> Int nextQ b pk qk = (qk - b) `mod` pk```

Then we sieve one block and convert the values to the primes:

```sieveBlock :: [Int] -> [Int] -> [Int] -> [Int] sieveBlock [] [] blk = blk sieveBlock (p:ps) (o:ofs) blk = filter f (sieveBlock ps ofs blk)   where     f x = (x < o) || ((x - o) `mod` p /= 0)   getValsfromBlock :: Int -> [Int] -> [Int] getValsfromBlock l bl = map (\x->l+1+2*x) bl ```

Now, it’s time to obtain all the numbers. This post will make use of the until function which is very similar to what some will use for the `for` construct in C.

```sieve :: Int -> Int -> Int -> [Int] -> [Int] sieve l r b primes = middle \$ until stop incr start   where     middle (_, v, _) = v     stop (sb, _, _) = sb == r     start = (l, [], map (firstQ l) primes)     incr (startblock, primessofar, q) = (nextblock, nextprimes, nextq)       where         array = [0 .. b-1]         nextblock = startblock + 2 * b         nextprimes = primessofar ++ (getValsfromBlock startblock bl)         nextq = zipWith (nextQ b) primes q         bl = sieveBlock primes q array```

The main is very simple after we know about the print function and that it is a monadic one

`main = print \$ sieve 100 20000 10 [3, 5, 7, 11, 13]`

That’s all for now.

### A Strange Machine

Another Haskell puzzle. This time, we have a 2D square matrix. Each cell can contain a number. We have a cursor which always resides in one cell of the matrix. Let s be the sum of values contained in the 8 neighbouring cells and the cursor’s cell. At each update step, we will modify the cell under cursor by using a bijective function of s. After this, we change the cursor location by moving it to a neighbouring cell or leaving it as it is, depending on the value of its cell.

We have to simulate such a machine, assuming that the matrix wraps at the boundary.

### A General Network Module

Let’s say we need to solve a problem involving a graph-like structure, possibly containing cycles. We want to do this in a functional way (Haskell) but we are stuck when we deal with the cycles.

### Numbers, exponents and cycles

Suppose we have a number $N_0$. We apply the following procedure to $N_0$ in order to obtain a new number $N_1$: we take $N_0$‘s digits and raise them alternatively to 2 and 4, summing the results. Thus, $N_0=2435$ will become $N_1=2^4+4^2+3^4+5^2=138$. We don’t stop here. Instead, we apply the same procedure to $N_1$ obtaining $N_2=1^2+3^4+8^2=146$.

Of course, and someone can prove it, this procedure will quickly lead either to a number already seen or to 1. For now, we are only interested in the number of iterations required for this.

### A Puzzle and a Solution (2)

Last post was ended with a problem: our solution exhausted the memory before it could give an answer to $N=1000$, $P=42$. There were three comments trying to solve them and the last two of them are working. However, the solution involving the lcm of cycles is faster and I will post it here (the other one is posted as a comment there).