# Accessing list elements when counting the number of rectilinear paths

Posted on

Problem

I am trying to solve the RIVALS problem on SPOJ: Starting from (0, 0), how many paths are there to reach point (X, Y), only taking one-unit steps moving to the right or up? Constraints: 0 ≤ X ≤ 106, 0 ≤ Y ≤ 106, answer is to be given modulo (109 + 7).

I am facing a performance issue with accessing elements of a list. I am also facing a runtime error if I am trying to access the list element.

In order to get the nth element I am using [1,1,1,2]!!n, but I have been told that this runs in O(n) which is very slow. Is there any other data structure in Haskell which gives O(1) access time for nth element?

About my algorithm: the number of way to move form (0,0) to (x,y) in 2D plain and answer is:

(x+y)!x! y!

{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Data.List
import Data.Bits
import Data.Maybe
import qualified Data.ByteString.Char8 as C

seqI :: Integer -> Integer
seqI x = seq x x

seqB :: Bool -> Bool
seqB x = seq x x

modExp' :: Integer -> Integer -> Integer -> Integer -> Integer
modExp' r b p m = let nextR = seqI $(seqI$ r*b)rem m
nextB = seqI $(seqI$ b*b)rem m
nextP = seqI $shiftR p 1 incl = seqB$ testBit p 0
cont  = seqB $nextP /= 0 in if incl then if cont then modExp' nextR nextB nextP m else nextR else if cont then modExp' r nextB nextP m else r modExp :: Integer -> Integer -> Integer -> Integer modExp b p m = modExp' 1 b p m readInts :: IO [Int] readInts = fmap (map read.words) getLine read2Ints :: IO [Int] read2Ints = do ints <- readInts if length ints == 2 then return ints else do putStrLn ("sorry, could you give me exactly two integers, " ++ "separated by spaces?") read2Ints p = 1000000007::Integer ip = 1000000005::Integer mtimes a b = (a * b)remp facts = scanl mtimes 1 [1..2000001] anstable ::[Integer] anstable = facts solve ::Int->Int-> Integer solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)rem1000000007 main :: IO () main = do n <- readLn forM_ [1..n::Int] (i -> do xs <- read2Ints print$(solve (head xs) (last xs)))


Solution

## Code organization

The definitions of readInts and read2Ints disrupt the mathematical code. The I/O routines belong further down, just before main.

import Data.Maybe and import qualified Data.ByteString.Char8 as C appear to be superfluous.

## Abstraction

It is not immediately obvious from reading

solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)rem1000000007


that it is calculating

(x+yy)=(x+y)!x! y!modp

I would expect to see

solve x y = modCombination (x + y) y p

modCombination n r p =
(factorial n) * (modInvFactorial r) * (modFactorial (n - r)) rem p'
where …


In some ways, you come close, but anstable obscures your intention. Why not ansTable, with the customary capitalization so that it doesn’t look like an stable? Why did you rename it from fact in the first place, making it more confusing? Why is 1000000007 hard-coded at the end, when you could have used p?

What is ip? 1000000005 is a magic number that appears nowhere in the stated challenge. What about 2000001? Where did that limit come from?