#-----------------------------------------------------------------------
# randomsurferhistogram.py
#-----------------------------------------------------------------------

import stdio
import stdarray
import stddraw
import sys
import random

# Accept an integer moveCount as a command-line argument. Read a
# transition matrix from standard input. Perform moveCount moves as
# prescribed by the transition matrix, and write to standard output
# the relative frequency of hitting each page. Also draw a histogram
# of the page ranks to standard draw.

moveCount = int(sys.argv[1])
pageCount = stdio.readInt()
stdio.readInt() # Discard the second int of standard input.

# Read the transition matrix from standard input.
# probs[i][j] is the probability that the surfer moves from
# page i to page j.
probs = stdarray.create2D(pageCount, pageCount, 0.0)
for i in range(pageCount):
    for j in range(pageCount):
        probs[i][j] = stdio.readFloat()

# Initialize stddraw.
stddraw.setXscale(-1, pageCount)
stddraw.setYscale(0, moveCount)

# Perform the simulation, thus computing the freqs array.
# freqs[i] is the number of times the surfer hits page i.
freqs = stdarray.create1D(pageCount, 0)
page = 0 # Start at page 0.
for i in range(moveCount):
    # Make one random move.
    r = random.random()
    total = 0.0;
    for j in range(0, pageCount):
        # Find interval containing r.
        total += probs[page][j]
        if r < total:
            page = j
            break
    freqs[page] += 1

    #if i % 1000 == 0:
    if i % 100000 == 0:
        # Plot histogram of frequencies
        stddraw.clear()
        for k in range(pageCount):
            #xCoords = [k-.25, k-.25,    k+.25,    k+.25]
            #yCoords = [0,     freqs[k], freqs[k], 0]
            #stddraw.filledPolygon(xCoords, yCoords)

            stddraw.filledRectangle(k-0.25, 0, 0.5, freqs[k])        
            stddraw.show(0)

# Write the page ranks.
for freq in freqs:
    stdio.writef("%8.5f", float(freq) / float(moveCount))
stdio.writeln()

stddraw.show()

#-----------------------------------------------------------------------

# python transition.py < tiny.txt | python randomsurferhistogram.py 1000000

# python transition.py < medium.txt | python randomsurferhistogram.py 1000000