乙Py先生のプログラミング教室
初学者のためのプログラミング学習サイト

Python

本日は暇な時の時間潰しにぴったりな
方形を数えるプログラムについてです


解説動画はこちら




問題

次の図形の中に正方形または長方形は
幾つあるでしょうか?
(黒塗りの部分が図形で 5x3 マスです)


download




探索プログラムの考え方


今回は四角形を探索するプログラムです

図形を黒を1 白を0でデータ化したのち
黒塗りの部分で作られる方形が
幾つあるのかを左上から順番に数えていきます。

起点を左上とし、そこから縦と横に
1マスずつ伸ばして数えていきます。

途中白(0)があったら探索を抜けて次に進みます。

こんな感じで探していきます。




方形を数えるコード

コードはこんな感じになります。
import matplotlib.pyplot as plt
import numpy as np

# 指定された左上(top, left)を基準に黒い長方形を数える
def count_black_rectangles_from_top_left(grid, top, left):
    # 左上が黒でなければカウントしない
    if grid[top][left] != 1:
        return 0  
    rows, cols, count = len(grid), len(grid[0]), 0
    
    # 指定された左上から長方形を探索
    for bottom in range(top, rows):
        for right in range(left, cols):
            # 長方形内がすべて黒かを確認
            if all(grid[i][j] == 1 for i in range(top, bottom + 1) for j in range(left, right + 1)):
                count += 1
            else:
                # 白いセルが見つかったらその方向は探索不要
                break  
    return count

# グリッド内のすべての黒い長方形を数える
def count_black_rectangles(grid):
    rows, cols, total_count = len(grid), len(grid[0]), 0
    for top in range(rows):
        for left in range(cols):
            total_count += count_black_rectangles_from_top_left(grid, top, left)
    return total_count

# グリッドのプロット
def plot_grid(grid):
    plt.figure(figsize=(6, 4))
    plt.imshow(np.array(grid), cmap="binary", interpolation="nearest")
    plt.title("Grid Visualization")
    plt.axis("off")
    plt.show()

# ブロックのカウントの実行

# グリッドの初期配置
grid = [
    [1, 1, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 1, 0],
]
plot_grid(grid)
result = count_black_rectangles(grid)
print(f"Number of black rectangles: {result}")

ぜひGoogle Colabなどにコピペして
試してみてください

もっと大きな16x16でやると
こうなります。

22
# ブロックのカウントの実行

# グリッドの初期配置
grid = [
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
]

plot_grid(grid)
result = count_black_rectangles(grid)
print(f"Number of black rectangles: {result}")


何個あるのかは数えてみてくださいね

こういった探索プログラムは
アルゴリズムを考える基本にもなり
プログラミングの上達にも役立ちますね!!!


今回は暇つぶしにぴったりな
方形を数えるプログラムについてでした

それでは


今回は画像に隠しメッセージを仕込める技術
ステガノグラフィーのご紹介です。


解説動画はこちら



ステガノグラフィーとは


ステガノグラフィー(Steganography)
画像、音声、動画などのデジタルデータに
別の情報を隠す技術のことです

これにより、情報を目に見えない形で
秘匿することができます。

早速情報を仕込んだ画像を作成してみましょう



ステガノグラフィーの仕組み

画像への埋め込み

最下位ビット(LSB)を利用して
画像の色をわずかに変更しメッセージを隠します。

最下位ビット(Least Significant Bit):
二進数の右端に位置する値

バイナリ変換:
メッセージをバイナリ形式に変換し終了ビットを追加

ピクセルの変更:
各ピクセルのRGB成分の最下位ビットを変更して
メッセージを埋め込み



ビット演算

変更対象のRGB値の各成分は0から255の範囲の整数
~1 は、ビット反転演算子

1 のビットを反転すると、全てのビットが反転し
...11111110 というビット列になる

RGB値 が 5の場合(バイナリで 00000101)
~1 は ...11111110 となり
5 & ~1 は 00000101 & 11111110 となり
結果は 00000100(つまり 4)になる

00000101 &
11111110



00000100


ピクセルの変更

各ピクセルのRGB成分から最下位ビットを取得し
バイナリメッセージの値に変更します


メッセージの復元

バイナリメッセージを8ビットごとに分割し、文字に変換
終了ビット(11111111)が見つかるまでメッセージを復元する



音声ファイルや動画ファイルにも同様の手法が使われ
音声の波形や動画のフレームに情報を埋め込むことが可能です。


埋め込む画像


元画像はこんな感じです。
sample





画像にメッセージを埋め込むコードサンプル

from PIL import Image

def encode_image(image_path, secret_message, output_path):
    # 画像を開く
    image = Image.open(image_path)
    encoded_image = image.copy()

    # メッセージをバイナリに変換
    binary_message = ''.join(format(ord(char), '08b') for char in secret_message) + '11111111'  # 終了ビット
    data_index = 0

    # 画像のピクセルを走査
    for y in range(encoded_image.height):
        for x in range(encoded_image.width):
            pixel = list(encoded_image.getpixel((x, y)))
            for i in range(3):  # RGBの各成分
                if data_index < len(binary_message):
                    pixel[i] = (pixel[i] & ~1) | int(binary_message[data_index])  # 最下位ビットを変更
                    data_index += 1
            encoded_image.putpixel((x, y), tuple(pixel))
            if data_index >= len(binary_message):
                break
        if data_index >= len(binary_message):
            break

    encoded_image.save(output_path)

# 使用例
input_img_path = "画像のパス"
input_message = "埋め込むメッセージ"
output_img_path = "出力後のパス"
encode_image(input_img_path, input_message, output_img_path)

実行するとメッセージを埋め込んだ画像が生成されます。

元の画像と比較すると

download


差分はほとんどわからないですね!!


画像からメッセージを取り出すコードサンプル

from PIL import Image

# バイナリメッセージを8ビットごとに分割して文字に変換
def make_message(binary_message):
    message = ''
    for i in range(0, len(binary_message), 8):
        byte = binary_message[i:i+8]
        if byte == '11111111':  # 終了ビットを検出
            break
        message += chr(int(byte, 2))
    return message

def decode_image(image_path):
    image = Image.open(image_path)
    binary_message = ''

    # 画像のピクセルを走査
    for y in range(image.height):
        for x in range(image.width):
            pixel = image.getpixel((x, y))
            for i in range(3):  # RGBの各成分
                binary_message += str(pixel[i] & 1)  # 最下位ビットを取得

    return make_message(binary_message)

# 使用例
decoded_message = decode_image('output_image.png')
print("Decoded message:", decoded_message)
Decoded message: Hello Otupy

メッセージが復元されました。




最後に

こちらの画像にはメッセージを埋め込んでいるので
ダウンロードして解読してみてくださいね

bbbb




今回はステガノグラフィーをご紹介しました
画像などに隠しメッセージを残せるので

暗号のように秘匿したいやりとりで
使うこともできたりして
なかなか面白い技術です。

いろいろ遊んでみてみてくださいね
それでは



今回は重力レンズエフェクトで
画像を歪ませで遊んでみました。


解説動画はこちら


 

重力レンズとは

光が天体の重力によって曲げられ
天体があたかもレンズとして働く効果のことです

光の曲がり具合はレンズとなる天体の質量が大きいほど強く
背後の銀河から来る光が強く曲げられて像が大きく歪んで見えます


今回はレンズをブラックホールで想定して
擬似的な効果の計算で画像を作成するコードのご紹介です。


基本の計算式

レンズ中心からの距離が小さくなるほど
(レンズに近づくほど)歪みが強くなるような計算です

元々の重力レンズの計算は少し難解かなと思いましたので
簡易な計算でエフェクトをかけます。

スクリーンショット 2024-11-23 17.08.32




処理の流れ

入力画像をNumPy配列に変換し、全ピクセルの座標を計算
重力レンズ効果を適用する領域を特定

レンズ中心からの距離に基づいて歪みを計算し、新しいピクセル座標を算出
新しい座標に基づいてピクセルを再配置し、ブラックホール領域を黒で塗りつぶし
最終的な画像として出力


ipywidgets でUIを作って操作できます。
スライダーの値を変えると、画像が変化します。

Google colabなどで試す事ができます。


コードはこちら
from PIL import Image, ImageDraw
import numpy as np
import matplotlib.pyplot as plt
from ipywidgets import interact, IntSlider, FloatSlider

cached_image = None

# 重力レンズエフェクトをかけた画像を生成する
def apply_gravitational_lens(image, lens_radius, black_hole_radius, distortion_factor):
    
    # 画像をNumPy配列に変換
    input_pixels = np.array(image)
    width, height = image.size
    cx, cy = width // 2, height // 2
    
    # 座標グリッドの生成と中心からの相対座標,距離の計算
    y, x = np.meshgrid(np.arange(height), np.arange(width), indexing="ij")
    dx, dy = x - cx, y - cy
    sx, sy = x.copy(),y.copy()
    distance = np.sqrt(dx**2 + dy**2)

    # 歪みを適用 { distortion = 1+distortion_factor * ((lens_radius - distance[lens_mask]) / lens_radius)**2 }
    lens_mask = (black_hole_radius < distance) & (distance < lens_radius)
    distortion = 1 + distortion_factor * ((lens_radius - distance[lens_mask]) / lens_radius)**2
    sx[lens_mask] = cx + dx[lens_mask] * distortion
    sy[lens_mask] = cy + dy[lens_mask] * distortion

    # 座標のクリッピングと出力画像の生成
    sx = np.clip(sx, 0, width - 1).astype(int)
    sy = np.clip(sy, 0, height - 1).astype(int)
    output_pixels = input_pixels[sy, sx]

    # ブラックホール領域の適用
    black_hole_mask = distance <= black_hole_radius
    output_pixels[black_hole_mask] = [0, 0, 0]
    return Image.fromarray(output_pixels)

# インタラクティブUI部
def interactive_gravitational_lens(image_path):

    global cached_image
    if cached_image is None:
        cached_image = Image.open(image_path).convert("RGB") 

    def update(lens_radius, black_hole_radius, distortion_factor):
        output_image = apply_gravitational_lens(
            cached_image,
            lens_radius=lens_radius,
            black_hole_radius=black_hole_radius,
            distortion_factor=distortion_factor,
        )
        plt.figure(figsize=(8, 8))
        plt.imshow(output_image)
        plt.axis('off')
        plt.title(f"Lens Radius: {lens_radius:03}, Black Hole Radius: {black_hole_radius:03}, Distortion: {distortion_factor:.02}")
        plt.show()

    interact(
        update,
        lens_radius=IntSlider(min=50, max=990, step=10, value=50, description="Lens Radius"),
        black_hole_radius=IntSlider(min=10, max=200, step=5, value=10, description="Black Hole Radius"),
        distortion_factor=FloatSlider(min=0.1, max=10.0, step=0.1, value=0.1, description="Distortion Factor"),
    )

interactive_gravitational_lens("画像パス")

download-1

レンズの半径と
歪み具合を調整して
面白画像を作って遊んでみてください。

動画では色々な画像で試しているので
ぜひみてみてくださいね

今回はこれまでです
それでは。




今回は円周率を計算するアルゴリズムを使って
馬鹿でかい円周率を行けるだけ求めてみました

解説動画はこちら





まず最初に問題ですが
円周率の小数点10000桁目の数値は
何になるでしょうか?

こんな問題を解く場合に
馬鹿でかい円周率を求める方法があります。



ガウス=ルジャンドルのアルゴリズム
(Gauss–Legendre algorithm)


円周率を計算する際に用いられる
数学の反復計算アルゴリズム(算術幾何平均法)

円周率計算のアルゴリズムの中でも
トップクラスの収束速度なので、精度が良いらしいです。

アルゴリズムは

スクリーンショット 2024-11-09 16.46.34

となります。


円周率を求める関数のコード

計算精度を設定して、その桁数までを求めていく感じになります。
例えば円周率の小数点100桁まで求めたかったら
計算精度を110-150 とかに設定します。

また反復計算の回数は
log2(x) 以上の回数が必要になるので
計算精度を上げる場合は、反復計算回数も
あわせて上げてください(ここでは20回にしてます)

from decimal import Decimal, getcontext

# 計算精度の設定(小数点以下1万桁以上の精度を確保)
getcontext().prec = 15000

# ガウス=ルジャンドルのアルゴリズムの実装
def gauss_legendre_pi():
    # 初期値設定
    a = Decimal(1)
    b = Decimal(1) / Decimal(2).sqrt()
    t = Decimal(1) / Decimal(4)
    p = Decimal(1)

    # 十分な収束回数で反復計算(math.ceil(math.log2(x))以上)
    for _ in range(20):
        a_next = (a + b) / 2
        b = (a * b).sqrt()
        t -= p * (a - a_next) ** 2
        a = a_next
        p *= 2

    pi_approx = ((a + b) ** 2) / (4 * t)
    return pi_approx

# 円周率の計算
pi_approx = gauss_legendre_pi()
pi_str = str(pi_approx)

# 1万桁目の数値を取得
k = 10000

# 結果を出力
print(f"円周率の小数点以下{k}桁目の数値: {pi_str[k+1]}")
9




まとめ

このPythonコードであれば小数点10万桁くらいまでは余裕です。

それ以上になるとハイスペックな計算資源が必要で
加えてもっと効率の良い高精度計算専用のライブラリを用いたり
並列分散処理などを実装する必要が出てくるかもしれません。

ちなみにこのアルゴリズムでは
2009年に筑波大学の高橋大介という方が
2兆5769億8037万桁
という記録を出しているので
そこから15年以上経った今なら
もっと馬鹿でかい桁まで計算が出来るかもしれません!!

デカいって、いいですよね
男のロマン

どなたか馬鹿でかい円周率の計算
挑戦してみませんか

今回はここまでです
それでは。

 

今回はあの有名な
クイズ番組の問題のシミュレーションです。


解説はこちら


 
モンティホール問題

3つのドアの中に景品の車が一つ有り
プレイヤーは1つのドアを選択できる
3door

プレイヤーがドアを選択した後、司会者モンティーは
そのドア以外のハズレのドアを開く
monty2

最後にプレイヤーはドアを変えるか
そのままかを選ぶ事が出来る


プレーヤーが1つのドアを選択したあと
外れのドアが1つ開放される

残り2枚の当たりの確率は直感的には
それぞれ 50% になるように思えるが
はたしてそれは正しいだろうか...





解説


開けるドアを
変える場合 と 変えない場合
勝率がどうなるのかを計測します。


シミュレーションコードはこちら
import random

def monty_hall_simulation(num_doors=3, num_trials=10000):
    switch_wins,stay_wins = 0,0

    for _ in range(num_trials):
        # 車を隠すドアをランダムに選ぶ
        doors = ['goat'] * (num_doors - 1) + ['car']
        random.shuffle(doors)
        car_index = doors.index('car')

        # プレイヤーが最初に選ぶドアをランダムに選ぶ
        player_choice = random.randint(0, num_doors - 1)

        # モンティが開けるドアを決定する(車とプレイヤーの選択以外)
        monty_choices = [i for i in range(num_doors) if i != player_choice and i != car_index]
        monty_opened = random.sample(monty_choices, num_doors-2)

        # プレイヤーがドアを変更する場合の勝敗
        switch_choice = next(i for i in range(num_doors) if i != player_choice and i not in monty_opened)
        if doors[switch_choice] == "car":
            switch_wins += 1

        # プレイヤーがドアを変更しない場合の勝敗
        if doors[player_choice] == "car":
            stay_wins += 1

    print(f"スイッチした場合の勝率: {switch_wins / num_trials * 100:.4f}%")
    print(f"スイッチしなかった場合の勝率: {stay_wins / num_trials * 100:.4f}%")

# シミュレーション実行
num_doors = 3
num_trials = 10000
monty_hall_simulation(num_doors=num_doors, num_trials=num_trials)
スイッチした場合の勝率: 67.1900%
スイッチしなかった場合の勝率: 32.8100%


この場合
開けるドアを変えた場合は 3分の2
変えない場合は3分の1
の確率で景品を得る事ができます。

つまり、開くドアを変えた方がお得で
約67%の確率で当たりを引けます。

残るのが2個のドアだから50%の確率というのは
まやかしでした。

ちなみにドアの数が増えれば増えるほど
ドアを変えた方が勝率は高くなります。

こんな感じで、直感的に迷う問題でも
プログラムであればシミュレーション出来るので
正しい答えを導き出せる手助けになります。

色々試してみてください
それでは。



このページのトップヘ