c – Random walk on a grid

// generate a random "walk" of letters from A to Z in a 2D grid, assuming a 
// character set with contiguous values of uppercase letters (e.g. ASCII); 
// stops if the "walker" gets stuck
// example of a successful walk:

//  A  .  .  .  I  J  K  .  .  . 
//  B  C  F  G  H  .  L  .  .  .
//  .  D  E  .  .  .  M  .  .  .
//  .  .  .  .  .  O  N  .  .  .
//  .  .  .  .  .  P  .  .  .  .
//  .  .  .  .  .  Q  .  .  .  .
//  .  .  .  .  .  R  S  .  .  .
//  .  .  .  .  .  .  T  U  .  . 
//  .  .  .  .  .  .  .  V  W  Z
//  .  .  .  .  .  .  .  .  X  Y

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <ctype.h>

#define GRID_SIZE 10

// movement directions
#define DIR_NUM 4

#define UP      0
#define LEFT    1
#define DOWN    2
#define RIGHT   3
#define ANY     (-1)

bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid(rows)(cols));
void generate_random_walk(size_t rows, size_t cols, char grid(rows)(cols));
void print_array(size_t rows, size_t cols, char grid(rows)(cols));

int main(void)
{
    char grid(GRID_SIZE)(GRID_SIZE) = { 0 };

    generate_random_walk(GRID_SIZE, GRID_SIZE, grid);
    print_array(GRID_SIZE, GRID_SIZE, grid);

    return 0;
}

void print_array(size_t rows, size_t cols, char grid(rows)(cols))
{
    for (size_t r = 0; r < rows; ++r) {
        for (size_t c = 0; c < cols; ++c) {
            char grid_c = grid(r)(c);
            printf(" %c ", isalpha(grid_c) ? grid_c : '.');
        }
        putchar('n');
    }
}

// checks all the directions by default (ANY)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid(rows)(cols))
{
    bool cangoup    = (rpos > 0) && grid(rpos - 1)(cpos) == 0;
    bool cangoleft  = (cpos > 0) && grid(rpos)(cpos - 1) == 0;
    bool cangodown  = (rpos < rows - 1) && grid(rpos + 1)(cpos)  == 0;
    bool cangoright = (cpos < cols - 1) && grid(rpos)(cpos + 1)  == 0;

    switch (dir) {
    case UP:    return cangoup;
    case LEFT:  return cangoleft;
    case DOWN:  return cangodown;
    case RIGHT: return cangoright;
    default:    return cangoup || cangoleft || cangodown || cangoright; // ANY
    }
}

void generate_random_walk(size_t rows, size_t cols, char grid(rows)(cols))
{
    size_t rpos, cpos;

    srand((unsigned int) time(NULL));

    rpos = cpos = 0;
    grid(0)(0) = 'A';
    for (char c = 'B'; c <= 'Z' && can_move(ANY, rpos, cpos, rows, cols, grid); c++) {
        // move in a random direction
        for (int dir;;) {
            dir = rand() % DIR_NUM;
            if (can_move(dir, rpos, cpos, rows, cols, grid)) {
                switch (dir) {
                case UP:    --rpos; break;
                case LEFT:  --cpos; break;
                case DOWN:  ++rpos; break;
                case RIGHT: ++cpos; break;
                default:
                    printf("Impossible movement direction.n");
                    exit(EXIT_FAILURE);
                }
                break; // break out of the loop
            }
        }

        // leave a trail
        grid(rpos)(cpos) = c;
    }
}

To summarize, this program prints a grid with a random walk of uppercase letters in order. If the “walker” cannot move in any direction due to lack of space around it (up, down, left, and right), the walking terminates.

What I’m interested in, aside from general tips regarding my code that you may be able to give me, are two things:

  1. I’ve read that functions shouldn’t normally take more than 2–3 parameters; do you think my functions really “suffer” from taking more than 3 parameters, and if so, how would I go about mitigating that?

  2. Should I be using a size_t when looping over an array or similar, or should I use an int instead? I’ve read here on Stack Exchange various opinions concerning this: some people say size_t should always be used since it’s essentially undefined behavior if the array’s size is greater than MAX_INT, etc., while others say unsigned and signed types ought not to be mixed (and I generally have to use them in expressions that undergo the usual arithmetic conversions), and this is a major source of bugs. Pragmatically, I believe I should therefore use a regular int. There’s another thing I’ve noticed, and that is if I have to actually use these counters to perform some calculation: in those cases I really have no recourse, and what I end up doing is simply casting and praying, hoping that the array is of a reasonable size (i.e. that my size_t counter, or the result of the expression isn’t out of the representable range for an int). I think this is even worse than using an int from the beginning, since the interface that the size_t type provides is not conformed to, so my code is “lying” to both itself and the reader.

Note that I would use an enum instead of the #define definitions for the directions, but my book hasn’t gotten to them yet, so I think we shouldn’t focus on this. Also, I’ve looked at other questions with this same exercise, but the code/approach presented there is somewhat different.

random – This code is a non-static C# class for rolling a number of dice

Fellow human beings, today I present to you my dice rolling script! Behold, in my amateurish attempt at some raw C# code. Perhaps this will remain here regardless of the dozens of other dice rolling scripts out there.

Contains a ‘for’ loop, a ‘switch’, and a method that returns a value.

I have indeed read through other, similar iterations of this class, and I have found them to be lacking in what I might learn from, usually due to over-complication for my tiny brain, or because it invoked the use of libraries I have yet to hear of.

I did my best to make it easy to read for whichever intrigued person stumbles upon this. I deeply respect and appreciate any who may take the time to offer any criticism on my code. What did I do right? What did I do wrong? I don’t have anyone or anywhere else to share it with.

using System;

namespace C_
{
    class RollDice : Program
    {


        //Variables

        int numOfDice;
        int numOfSides;

        int maxDice = 100;
        int minDice = 1;
        int maxSides = 100;
        int minSides = 1;
        int totalRolled;

        //Start method for number of Dice to throw - take the player input in InputMethod() which returns an int. If returning 0, then restart. Clamp the value between min/max. Continue to next function.

        public void GetDice()
        {
            Console.WriteLine("Welcome to Roll Dice!");
            Console.WriteLine("How many dice do you want to throw?");
            numOfDice = InputMethod();
            if(numOfDice == 0)
            {
                GetDice();
            }
            if (numOfDice > maxDice || numOfDice < minDice)
            {
                numOfDice = Math.Clamp(numOfDice, minDice, maxDice);
                Console.WriteLine($"Number of Dice set to {numOfDice}");
            }

            GetSides();
        }

        // Get the sides of each dice by using a similar process. Roll() for each dice, then sum the totals in RollTotal().

        public void GetSides()
        {
            Console.WriteLine("How many sides does each dice have?");
            numOfSides = InputMethod();
            if(numOfSides == 0)
            {
                GetSides();
            }
            if (numOfSides > maxSides || numOfSides < minSides)
            {
                numOfSides = Math.Clamp(numOfSides, minSides, maxSides);
                Console.WriteLine($"Number of Sides set to {numOfSides}");
            }

            for (int x = 1; x <= numOfDice; x++)
            {
                Roll();
            }

            RollTotal();
        }


        // Create a new Random() instance for the number of sides and add it to the totalRolled variable.

         public void Roll()
        {
            Console.WriteLine(".....");
            Console.WriteLine("Rolling");
            Random r = new Random();
            var result = r.Next(1, numOfSides + 1);
            Console.WriteLine($"You rolled {result}");
            totalRolled += result;
        }
        
        // Output the total and prompt to roll again or quit. Reset the total..

        public void RollTotal()
        {
            Console.WriteLine($"Total sum rolled is {totalRolled}");
            Console.WriteLine(" ");
            Console.WriteLine("Enter 1 to re-roll or 2 to quit.");
            var answer = InputMethod();

            switch (answer)
            {
                case 0:
                RollTotal();
                break; 
            
                case 1:
                totalRolled = 0;
                GetDice();
                break;           
            
                case 2:
                totalRolled = 0;
                Environment.Exit(0);
                break;
            
                default:
                Environment.Exit(0);
                break;
            }
        }

        //Convert the input to an integer if valid and return the value. Else return 0.

        public int InputMethod()
        {
            var input = Console.ReadLine();
            if(!Int32.TryParse(input, out int convertedStringToInt))

            {
                Console.WriteLine("You need to enter a valid number!");
                return 0;
            }
            
            else 
            
            {
                return Convert.ToInt32(input);
            }

        }

    }
}

differential equations – time dependent hamiltonian with random numbers

I have a Hamiltonian (Z) in matrix form, I solved it for time independent random real numbers, now want to introduce time dependent in such a way at any time the random real numbers change between the range {-Sqrt(3sigma2), Sqrt(3sigma2)}, here is my code

Nmax = 100; (*Number of sites*)

tini = 0; (*initial time*)

tmax = 200; (*maximal time*)

(Sigma)2 = 0.1; (*Variance*)

n0 = 50; (*initial condition*)

ra = 1; (*coupling range*)

(Psi)ini = Table(KroneckerDelta(n0 - i), {i, 1, Nmax});

RR = RandomReal({-Sqrt(3*(Sigma)2), Sqrt(3*(Sigma)2)}, Nmax);

Z = Table(
    Sum(KroneckerDelta(i - j + k), {k, 1, ra}) + 
     Sum(KroneckerDelta(i - j - k), {k, 1, ra}), {i, 1, Nmax}, {j, 1, 
     Nmax}) + DiagonalMatrix(RR);

usol = NDSolveValue({I D((Psi)(t), t) == 
     Z.(Psi)(t), (Psi)(0) == (Psi)ini}, (Psi), {t, tini, tmax});

What can I do for introduce this time dependent and solve the differential equation(usol)? I hope my question is clear

performance – Creating a specific distribution of random numbers in Powershell

I originally posted this on StackOverflow but was requested to post it here instead as it relates to optimization/performance of the code rather than a specific problem.

TL;DR: Get-Random produces an even distribution of numbers where every number in the pool has an even chance of appearing. I’m looking for a way to generate random numbers where every individual number appears with a frequency that I myself specify.


If I run

for($i=1;$i -le 1000;$i++){
    Get-Random -Minimum 0 -Maximum 10
}

I get a very evenly distributed count for each number (roughly 100 for each number between 0 and 9). Using Get-Random allows me to get a random number every time but on average, every individual result will appear roughly an equal amount of times. I want to decide the frequency for how often any specific number appears, and then generate random numbers that fit that distribution. As an example:

Number   Probability
0        10
1        11
2        19
3        12
4        3
5        10
6        6
7        7
8        4
9        18

I’m looking for a way to use the above list to randomly generate a number between 0 to 9, but with the probability of each individual number appearing using the Probability column.

My very hard-coded and not so generic solution so far is that I thought of doing something like adding a cumulative percentage column:

Number   Probability   CumulativeProbability
0        10            10
1        11            21
2        19            40
3        12            52
4        3             55
5        10            65
6        6             71
7        7             78
8        4             82
9        18            100

And from here, run the object through a filter. Something like:

$RandomNumber = Get-Random -Minimum 0 -Maximum 100
$MyProbabilityObject | Where-Object {$RandomNumber -ge $_.CumulativeProbability}

This gives me all numbers with a lower Cumulative probability than the random number. Let’s say the $RandomNumber was 42, that would result in:

Number   Probability   CumulativeProbability
0        10            10
1        11            21
2        19            40

From here, I could pipe the result to

Select-Object CumulativeProbability | Measure-Object -Property CumulativeProbability -Maximum 

Which gives me the highest value, and then use that column as a reference to find the number with

Where-Object {$_.CumulativeProbability -eq $TheNumberIGetAbove}

While this kinda works, it feels like I’m doing several laps around a problem that should be easier and more straightforward to solve. Are there any better ways of generating random numbers that fit a distribution you specify yourself instead of using an even distribution such as Get-Random?

terminology – random walk with discrete distribution without replacement

suppose there is a set of vectors $S = { s_1, s_2, cdots, s_n}, s_i in mathbb{R}^2$.

the “random walk” I am interested in is to start at $(0, 0)$,

1, sample a step $s_i$ from $S$ with equal probability.

2, sample second step $s_j$ from $Ssetminus {s_i}$ with equal probability.

3, repeat until all the steps have been enumerated.

Is there any field study on the properties of the trace of this type of “random walk”?

E.g. Expected position within $t$ steps. Convex hull density within $t$ steps.

probability theory – Given random variables X and Z, can I (symmetrically) constuct a Y such that X, Y, Z is a Markov chain?

The following problem is giving me a bit of a headache:

Let $X, Z$ be a pair of random variables.
Under which conditions can I construct a random variable $Y$ such that
$X, Y, Z$ is a Markov chain? In order to avoid trivial solutions such as $X=Y$ I additionally require the construction to be symmetrical with respect to $X$ and $Z$.
That is, if I change $X$ and $Z$ when defining $Y$, I obtain the same random variable.

I am thinking of $Y$ of some sort of variable that captures the common “information” between $X$ and $Z$. Maybe it even holds that $I(X, Y) = I(Y, Z)$?

So far I could only find such $Y$ if I assume $X$ and $Y$ to be correlated standard normal distributions. An answer under any (non totally trivial) assumption is welcome 🙂

How to generate a random matrix with arbitrary correlation between elements?

I would like to find a smart way to generate a $Ntimes N$ random matrix $M$ with arbitrary correlation:
begin{equation}
boxed{langle M_{ij}M_{kl}rangle=tau_{ijkl}}
end{equation}

Where the mean and variance of the elements are given by:
begin{align}
langle M_{ij}rangle&=0 \
langle M_{ij}^2rangle&=sigma^2
end{align}


The case I am interested in is actually a sub-problem of this. I would like to generate a matrix whose elements follow a normal distribution of mean $0$ and variance $1/N$, and whose elements are correlated the following way:
begin{equation}
langle M_{ij}M_{ki}rangle=tau_{ijk}
end{equation}

When $tau_{ijk}=delta_{jk}N^{-1}$ I recover a symmetric matrix.

AddTo operation to random element of a list yields unexpected results

I have a list of numbers. I want to randomly select one of those, with a probability proportional to its value, and increment it by one.

I tried this simple one-liner

my_list = {1,1,1}
my_list((RandomSample(my_list->Range(Length(my_list)))) += 1

and it works just fine as long as the elements of my_list are all identical. However, when my_list contains values that are not all identical, sometimes it fails spectacularly, e.g.:

SeedRandom(1)
my_list = {1,2,3}
my_list((RandomSample(my_list->Range(Length(my_list)))) += 1
{4,2,3}

My guess is that for some reason here RandomSample is called twice, once for deciding which number from my list is incremented by 1 and then another time to decide where to store the result of the operation. So in the above example first the number 3 is incremented by 1, and then the result is stored in position 1.

If this is the case, is this an expected behaviour? If not, can you explain it?

P.s. There is of course a trivial workaround, i.e. to store the result of RandomSample in a temporary variable and use that to index my_list. But here I would like to understand what is happening exactly in my one-liner.

P.p.s: to put things in perspective, the same thing e.g. in python would just work, that’s why I am particularly puzzled:

import numpy as np

my_list = np.array((1,2,3))
my_list(np.random.choice((0,1,2), p=my_list/my_list.sum())) += 1

algorithm analysis – Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates,this is an algorithm that solves the problem.

def subsetsWithDup(self, nums: List(int)) -> List(List(int)):
    
    nums.sort()
    res = (())
    self.dfs(nums, res, (), 0)
    return res

def dfs(self, nums, res, path, index):

    if path not in res:
        res.append(path)
    
    for pos in range(index, len(nums)):
        self.dfs(nums, res, path + (nums(pos)), pos+1)

I think the time complexity of this algorithm is : n * n! * 2^n,

My logic is as follows, we loop the array once per value (n)

For each loop the number of calls is (n-1)! which is n! complexity

Then there is a check if value in array in each call which has at most 2^n checks since thats when power set is complete but dupes are being checked

Combining them gives n*n!*2^n

Is this correct ?

Thank you