Code and Bugs

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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.

Read the rest of this entry »

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).

Read the rest of this entry »

Follow

Get every new post delivered to your Inbox.