FDM for the time dependent wave equation in Julia

I am writing a test code of our new time-dependent wave equation in Julia.

For now, it is equivalent to the normal wave equation and it looks fine.

I am not sure Julia is that fast and easy to write, but one of the merits is that the visualization functions can be called within Julia's framework.

 

Leetcode: Unique Paths

 To make some practice on DP, "Unique Paths"@Leetcode is solved.

Probably a typical one, and super easy.
https://leetcode.com/problems/unique-paths

import numpy as np

class Solution:

def uniquePaths(self, m: int, n: int) -> int:

dp = np.zeros((m,n),np.int32)

dp[0,:]=1

dp[:,0]=1

for j in range(1,m):

for i in range(1,n):

dp[j,i] = dp[j-1,i] + dp[j,i-1]

return dp[m-1][n-1]

Sudoku solver @LeetCode

 Not elegant at all, but readable sudoku solver.

https://leetcode.com/problems/sudoku-solver/

class Solution(object):

    

    def checkNew(self, i,j,k,board):

        

        for jj in range(9):

            if board[i][jj] == str(k):

                return False

        for ii in range(9):

            if board[ii][j] == str(k):

                return False

        

        iB = i//3

        jB = j//3

        b = []

        for ii in range(3):

            for jj in range(3):

                if board[3*iB+ii][3*jB+jj] == str(k):

                    return False

        

        

        return True

    

    def backtrack(self, board):

# Find a blank element. The search direction does not a matter,

# but row-oriented here.

        for i in range(9):

            for j in range(9):

                if board[i][j] == ".":

# If blank, try numbers from 1 to 9

                    for k in range(9):

                        if self.checkNew(i,j,k+1,board): # Check if k is OK            

                            board[i][j]=str(k+1)

                            if self.backtrack(board): # Try next blank until OK

                                return True

                            else:

                                board[i][j] = "." # if inconsistent, step back

                    else:

                        return False

        return True

    

    

    def solveSudoku(self, board):

        """

        :type board: List[List[str]]

        :rtype: None Do not return anything, modify board in-place instead.

        """

        self.backtrack(board)

Unique Paths III @LeetCode

Just to wake up; 

980. Unique Paths III
https://leetcode.com/problems/unique-paths-iii/

class Solution:

    

    def checkIfReachable(self,curPoint,walkable, grid):

        (i,j) = curPoint

        #print(curPoint)

        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):

            return 0

        

        if grid[i][j]==2:

            if len(walkable)==0:

                return 1

            else:

                return 0

        

        if curPoint not in walkable:

            return 0

        

        walkable.remove(curPoint)

        

        num1 = self.checkIfReachable((i+1,j  ),walkable.copy(),grid)

        num2 = self.checkIfReachable((i-1,j  ),walkable.copy(),grid)

        num3 = self.checkIfReachable((i  ,j+1),walkable.copy(),grid)

        num4 = self.checkIfReachable((i  ,j-1),walkable.copy(),grid)

        

        return num1+num2+num3+num4

    

    def uniquePathsIII(self, grid: List[List[int]]) -> int:

        

        walkable = []

        

        for i in range(len(grid)):

            for j in range(len(grid[0])):

                if grid[i][j] == 0:

                    walkable.append((i,j))

                elif grid[i][j] == 1:

                    walkable.append((i,j))

                    start = (i,j)

        

        numPath = self.checkIfReachable(start,walkable,grid)

        return numPath

An alternative to Google Photo: Moments@Synology NAS

 Since Google photo will not be free after 1 June, I started looking for an alternative.

One of the candidates for me is "Moments" on my Synology NAS (DS218play).

DS Photo might be the first option for photo management, but it does not handle 360-deg photos properly (it just show as a big flat one).

Basically, Moments looks nice, but it seems it spins up HDDs from hibernate (not quite sure. It could be the same before).

TDPC C

 というわけで、TDPC　C。

考え方は簡単で、
(1) 自分の対戦相手が今まで生き残ってくる確率
(2) 自分が勝てる確率
(3) 自分が今まで生き残って来れた確率

を掛け算して足しあわせると現在自分が勝ち上がれるかどうかの確率になる
（かどうか、いまいち直感的でないんだけど、答えはそれであってる）。

どっちかというと対戦相手を見つけてくるループが面倒で、私は予めリストアップした(groupがそれ)

https://atcoder.jp/contests/tdpc/submissions/18020128

import numpy as np

def calcProb(P,Q,R):

   RP = R[P]

   RQ = R[Q]

   prob = 1.0 / (1.0+10.0**((RQ-RP)/400.0))

   return prob

def calcConsequtiveProb(iP,iG,R,dp,iBat):

   prob = 0.0

   for i in iG:

      prob += calcProb(iP,i,R)*dp[iBat-1,i]

   return prob

N = int(input())

numPerson = 2**N

R = []

for i in range(numPerson):

   R.append(float(input()))

group = []

group.append([ [i] for i in range(numPerson)])

for i in range(1,N+1):

   locGroup = []

   prevGroup = group[i-1]

   for j in range(len(prevGroup)//2):

      lg1 = prevGroup[2*j  ]

      lg2 = prevGroup[2*j+1]

      locGroup.append(lg1+lg2)

   group.append(locGroup)

dp = np.zeros((N+1,numPerson),np.float)

dp[0,:] = 1.0

for iBat in range(1,N+1):

   locGrp = group[iBat-1]

   for iGrp in range(len(locGrp)//2):

      lg1 = locGrp[iGrp*2  ]

      lg2 = locGrp[iGrp*2+1]

      for iPerson in lg1:

         prob = calcConsequtiveProb(iPerson,lg2,R,dp,iBat)

         dp[iBat,iPerson] = dp[iBat-1,iPerson]*prob

      for iPerson in lg2:

         prob = calcConsequtiveProb(iPerson,lg1,R,dp,iBat)

         dp[iBat,iPerson] = dp[iBat-1,iPerson]*prob

for i in range(numPerson):

   print(f'{dp[N,i]:.8f}')

Quantum Fourier Transform (QFT) on Q# (3 qubits) Part2

 QFT with three qubits is implemented in Q#.
The last post was to initialize the original state (entangled over three qubits).
I feel the measurement part should be as this post (the last one is incorrect).

Formulation is;
https://dojo.qulacs.org/ja/latest/notebooks/2.3_quantum_Fourier_transform.html#

The result is;
|000>: 1000, others: 0.
This agrees with the result of the above site :)!

namespace QFT_naive {

    open Microsoft.Quantum.Canon;

    open Microsoft.Quantum.Intrinsic;

    open Microsoft.Quantum.Convert;

    open Microsoft.Quantum.Arrays;

    

    @EntryPoint()

    operation SayHello() : Unit {

        Message("Hello quantum world!");

        mutable counts = new Int[8];

        mutable nres0 = 0;

        mutable nres1 = 0;

        mutable nres2 = 0;

        for(trian in 1..1000){

        using ( (input) = (Qubit[3] ) ){

            // 1/sqrt(8) (|000> + |001> + ,,, + |111>)

            H(input[0]);

            H(input[1]);

            H(input[2]);

            // Star QFT

            // R1 = Z, R2=S, R3=T

            H(input[0]);

            (Controlled S)([input[1]],input[0]);

            (Controlled T)([input[2]],input[0]);

            H(input[1]);

            (Controlled S)([input[2]],input[1]);

            H(input[2]);

            SWAP(input[2],input[0]);

            //CNOT(input[0], input[2]);

            //CNOT(input[2], input[0]);

            //CNOT(input[0], input[2]);

            // Start Measuring

            let res0 = M(input[0]);

            let res1 = M(input[1]);

            let res2 = M(input[2]);

            if (res0 == Zero){

                set nres0 = 0;

            }else{

                set nres0 = 1;

            }

            if (res1 == Zero){

                set nres1 = 0;

            }else{

                set nres1 = 1;

            }

            if (res2 == Zero){

                set nres2 = 0;

            }else{

                set nres2 = 1;

            }

            let bit = nres0 + nres1*2 + nres2*4;

            set counts w/= bit <- counts[bit]+ 1;

            ResetAll(input);

        }

        }

        for (j in 0..7) {

           Message(IntAsString(counts[j]));

        }

    }

}

TDPC(Typical DP Contest) A

 二次元配列にしないで解いてる人もいるみたいだけど私にはさっぱりわからないのでとりあえず二次元で。
”これまでに作成可能な点数であることが確認できれば、現在確認中のスコアを足した点数も作成可能である”ことを二次元配列で表現。

最終的には、最後の行を見れば作れる点数の個数がわかる。

https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

import numpy as np

N = int(input())

line = input().split()

p = []

p.append(0)

for i in line:

   p.append(int(i))

dp = np.zeros((len(p),sum(p)+1),np.int8)

dp[0,0]=1

for j in range(1,len(p)):

   for i in range(0,sum(p)+1):

      if dp[j-1,i]:

         dp[j,i+p[j]] = 1

         dp[j,i] = 1

#print(dp)

print(sum(dp[len(p)-1,:]))

ABC129 C

DP の勉強のために下記ブログの問題リストを解いてみている。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

DPだとわかっているからできるけど、自分でいきなりはまだ思いつけなさそう。
https://atcoder.jp/contests/abc129/tasks/abc129_c

import sys

line = input().split()

N = int(line[0])

M = int(line[1])

dp = [0] * (N+1)

NA = [1] * (N+1)

for i in range(M):

   NA[int(input())] = 0

for i in range(N):

   if NA[i+1] == 0 and NA[i]==0:

      print(0)

      sys.exit(0)

dp[0] = 1

dp[1] = 1

for i in range(2,N+1):

   if NA[i] == 0:

      dp[i] = dp[i-1]

   elif NA[i-1] == 0:

      dp[i] = dp[i-1]

   else:

      dp[i] = dp[i-1]*NA[i-1] + dp[i-2]*NA[i-2]

print(dp[N]%1000000007)