乙Py先生のプログラミング教室

乙Py先生のプログラミング教室

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

Python

2つのバケツを使って水の量を測るっていう
古典的なパズル問題ありますよね

今回はそれをプログラムで解いてみました。

解説動画はこちら



二つのバケツで指定の水量を測るやつ

問題

5リットル入るバケツと3リットル入るバケツがある
この2つだけを使って4リットルの水を測りたい
どうすれば良いでしょうか

ヒント : 水は捨てたり移動したりして良い





プログラムでの解法

幅優先探索(breadth-first search, BFS)を
用いて手順の探索を行っていきます。

バケツをA, B、測りたい水量をXとし
A,Bの水量を記録していきます

途中、以下の6つの状態でうまく切り替えて手順を記録し
どこかが水量Xになったら終了になります。

1. Aを満たす
2. Bを満たす
3. Aを空にする
4. Bを空にする
5. AからBに移す
6. BからAに移す

プログラム上ではキューというデータ構造のものを使って
手順を記録していく形になります。


手順を解くコード

手順を算出するコードは次のようになります。

from collections import deque
from math import gcd

# 幅優先探索(breadth-first search, BFS)を用いて手順の探索を行う
def min_steps_to_measure(A, B, X):
    # 目標の水量がAとBの最大公約数で割り切れない場合は終了
    if X > max(A, B) or X % gcd(A, B) != 0:
        return []

    # キューとSETと状態の親を初期化
    queue, visited, parent = deque(), set(), {}

    # 初期状態をキューに追加
    queue.append((0, 0))  # (容器Aの水量, 容器Bの水量)
    parent[(0, 0)] = None  # 初期状態の親はNone

    while queue:
        a, b = queue.popleft()

        # 目標の水量に達した場合
        if a == X or b == X:
            # 結果を表示
            steps = []
            while (a, b) is not None:
                steps.append((a, b))
                # 親が存在する場合のみアンパック
                if parent[(a, b)] is not None:
                    a, b = parent[(a, b)]
                else:
                    break
            steps.reverse()
            return steps

        # 訪れた状態を記録
        if (a, b) in visited:
            continue
        visited.add((a, b))

        # 次の状態をキューに追加
        # 1. 容器Aを満たす
        if (A, b) not in visited:
            queue.append((A, b))
            parent[(A, b)] = (a, b)
        # 2. 容器Bを満たす
        if (a, B) not in visited:
            queue.append((a, B))
            parent[(a, B)] = (a, b)
        # 3. 容器Aを空にする
        if (0, b) not in visited:
            queue.append((0, b))
            parent[(0, b)] = (a, b)
        # 4. 容器Bを空にする
        if (a, 0) not in visited:
            queue.append((a, 0))
            parent[(a, 0)] = (a, b)
        # 5. 容器Aから容器Bに移す
        transfer_to_B = min(a, B - b)
        if (a - transfer_to_B, b + transfer_to_B) not in visited:
            queue.append((a - transfer_to_B, b + transfer_to_B))
            parent[(a - transfer_to_B, b + transfer_to_B)] = (a, b)
        # 6. 容器Bから容器Aに移す
        transfer_to_A = min(b, A - a)
        if (a + transfer_to_A, b - transfer_to_A) not in visited:
            queue.append((a + transfer_to_A, b - transfer_to_A))
            parent[(a + transfer_to_A, b - transfer_to_A)] = (a, b)

    return []  # 目標の水量を測ることができない場合





早速実行して見てみましょう。

バケツA,Bの値と
ターゲットの水量Xを指定すると
その手順が表示されます。

# 容器の容量と目標の水量を指定
A = 5  # 容器Aの容量
B = 3  # 容器Bの容量
X = 4  # 測りたい水量

# 最小手数を計算
steps = min_steps_to_measure(A, B, X)

# 結果を表示
if steps:
    print("途中の過程:")
    for step in steps:
        print(f"容器A: {step[0]}L, 容器B: {step[1]}L")
else:
    print("目標の水量を測ることができませんでした。")

途中の過程:
容器A: 0L, 容器B: 0L
容器A: 5L, 容器B: 0L
容器A: 2L, 容器B: 3L
容器A: 2L, 容器B: 0L
容器A: 0L, 容器B: 2L
容器A: 5L, 容器B: 2L
容器A: 4L, 容器B: 3L



このように探索の結果が表示されます。

文字だけだと分かりづらいので
描画してみることにしましょう。



手順を描画するコード

ipywidgetsでスライダーを作り
stepを可変で描画できます。

A,B,Xを色々な設定に変えて
色々遊んでみてください。

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import ipywidgets as widgets
from IPython.display import display
%matplotlib inline

A = 5  # 容器Aの容量
B = 3  # 容器Bの容量
X = 4  # 測りたい水量

steps = min_steps_to_measure(A, B, X)

# 描画関数
def draw_graph(step):
    a_value = steps[step][0]
    b_value = steps[step][1]
    a_frame_height = A - a_value
    b_frame_height = B - b_value

    # 描画
    fig, ax = plt.subplots(figsize=(8, 4))
    ax.bar(0, a_value, width=0.4, label='Container A Volume (L)', color='blue', linewidth=2, edgecolor='black')
    rect_a = patches.Rectangle((-0.2, a_value), 0.4, a_frame_height, linewidth=2, edgecolor='black', facecolor='none')
    ax.add_patch(rect_a)
    ax.text(0, max(A,B)+1, str(a_value), ha='center', va='bottom', fontsize=12, color='green')
    ax.bar(1, b_value, width=0.4, label='Container B Volume (L)', color='red', linewidth=2, edgecolor='black')
    rect_b = patches.Rectangle((0.8, b_value), 0.4, b_frame_height, linewidth=2, edgecolor='black', facecolor='none')
    ax.add_patch(rect_b)
    ax.text(1, max(A,B)+1, str(b_value), ha='center', va='bottom', fontsize=12, color='green')

    # タイトルとラベルの設定
    ax.set_title(f'Container A : {A} and B: {B} Target Volume : {X} with Frames step : {step}')
    ax.set_xlabel('Containers')
    ax.set_ylabel('Volume (L)')
    ax.set_xticks([0, 1])
    ax.set_xticklabels(['Container A', 'Container B'])
    ax.set_ylim(0, max(A,B)+3)
    plt.show()

# スライダーの作成
step_slider = widgets.IntSlider(value=0, min=0, max=len(steps)-1, step=1, description='Step:')
interactive_plot = widgets.interactive(draw_graph, step=step_slider)
display(interactive_plot)
step06


今回は2つのバケツを使って水量を測るやつを
プログラムにしてみました。

動画ではもう少し手順のかかるやつもやっているので
興味がある場合は見てみてください。

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


 
タグ ：
#Python
#プログラミング
#パズル
#バケツの水
#幅優先探索
#BFS

今回は日本人の年収ランキングを求めてみました

解説動画はこちら



問題

年収500万円の人は、日本の年収ランキングで
何位くらいになるでしょうか?

参考 : 日本の人口 1.245億 (2023年)





年収ランキングを求める



今回は本当に正しい値を求める事は難しいので
ザックリと近似値を求めていきます。

日本人の年収は
対数正規分布
というものに近似しています。

この分布を用いて
ざっくりと計算をしていきます。

今回は日本人の
人口が12450万人
平均年収 450万円
年収中央値を 350万円
で設定して行います。



年収分布と上位何%を計算するコード

対数正規分布と
おおよその順位を計算するコードです

Google Colabなどに貼り付けて
incomeのスライドを変えてみてください。
import numpy as np
import matplotlib.pyplot as plt
import math
import ipywidgets as widgets
from IPython.display import display
%matplotlib inline

# 対数正規分布のパラメータ設定
median_income = 350  # 中央値（単位: 万円）
mean_income = 450    # 平均値（単位: 万円）
sigma = math.sqrt(2 * math.log(mean_income / median_income)) # 標準偏差を計算
mu = np.log(median_income) # 対数正規分布の μ を計算

# x軸の範囲（年収100万円 ~ 3000万円）
x = np.linspace(100, 3000, 1000)

# パーセンタイルランクを計算する関数
def calc_percentile_rank(income):
    return 1 - 0.5 * (1 + np.sign(income - median_income) * np.sqrt(1 - np.exp(-((np.log(income) - mu) ** 2) / (2 * sigma ** 2))))

# プロットを更新する関数
def update_plot(income):
    # 確率密度関数 (PDF) を計算
    pdf = (1 / (x * sigma * np.sqrt(2 * np.pi))) * np.exp(-((np.log(x) - mu) ** 2) / (2 * sigma ** 2))
    percentile_rank = calc_percentile_rank(income) # ランク計算
    total_population = 124_500_000 # 日本の人口
    rank = (percentile_rank) * total_population
    plt.clf()
    
    # 確率密度関数をプロット
    plt.figure(figsize=(12, 4))
    plt.plot(x, pdf, label="Log-normal Distribution", color="blue")
    plt.axvline(income, color="red", linestyle="--", label=f"Income = {income}") # incomeの位置に線を引く
    plt.axvline(median_income, color='orange', linestyle='--', label=f"Median: {median_income}")
    plt.axvline(mean_income, color='green', linestyle='--', label=f"Mean: {mean_income}")
    plt.fill_between(x, pdf, where=(x >= income), color="lightblue", alpha=0.5) # income以上の範囲を薄い青で塗りつぶす
    plt.title(f"nensyu {income} : Top {percentile_rank*100:.4f}% , Rank {rank:.0f}", fontsize=14)
    plt.xlabel("Income", fontsize=12)
    plt.ylabel("Density", fontsize=12)
    plt.legend()
    plt.grid(alpha=0.5)
    plt.show()

# スライダーを作成
income_slider = widgets.IntSlider(value=500, min=100, max=3000, step=1, description='Income:')
interactive_plot = widgets.interactive(update_plot, income=income_slider)
display(interactive_plot)
download


まとめ
日本人の人口が12450万人
平均年収450万円
年収中央値350の設定では

年収500万円くらいの人の年収は
約上位32.76% : 4078万位くらいになる

年収3000万円以上の人は
0.25%くらいしかいないっぽいです
(約30万人)

自分の年収を入れて
どれくらいのランクになるか
遊んでみてくださいね

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




 
タグ ：
#Python
#プログラミング
#対数正規分布
#年収
#ランキング

今回は4x4のスライドパズルを解く
アルゴリズムの解説です


解説動画はこちら



スライドパズルを解くアルゴリズム


こんな感じのスライドパズルを

1 2 3 4
5 6 7 8
9 0 10 11
13 14 15 12

プログラムで解いていきます

今回は4つのアルゴリズムを用いて
スライドパズルを解いていきます

1. 幅優先探索 (BFS)
2. A* アルゴリズム
3. IDA* (Iterative Deepening A*)
4. モンテカルロ探索


各アルゴリズムの詳細

1. 幅優先探索 (BFS)
特徴: 全ての状態を探索してから
次の深さへ進む解を見つけるときは最短手数を保証
利点: 最短経路を必ず見つける
欠点: メモリ消費量が非常に大きい
4x4スライドパズルのような小規模な問題では問題ない

2. A* アルゴリズム
特徴: 幅優先探索の効率化版状態の評価にヒューリスティック関数を使用
利点: ヒューリスティック関数が良い場合、効率的に最適解を発見可能
欠点: メモリ消費が高く、ヒューリスティックが不適切だと探索が非効率になる

3. IDA* (反復深化 A*)
特徴: 深さ優先探索をA* ベースにしたアルゴリズムで
閾値を段階的に増やす
利点: メモリ使用量が少なく、大規模な問題に対応しやすい
欠点: 反復のため、特定の状態を何度も評価するため
時間効率はA*に劣ることがある

4. モンテカルロ探索
特徴: ランダムなシミュレーションで解を探す非決定的アルゴリズム
利点: 実装が簡単で、初期状態から短時間で結果を得られることが多い
欠点: 最適解を保証できず、試行回数による品質のばらつきが大きい


適用シナリオ

幅優先探索: 状態空間が小さく、メモリ制限が問題にならない場合
A*: 高精度のヒューリスティック関数を使い、効率的に最適解を探したい場合
IDA*: メモリ効率を優先しつつ、最適解を求める場合
モンテカルロ探索: 厳密な最適性が不要で、迅速におおよその解を得たい場合


スライドパズルを解くベースのコード

ここからはスライドパズルを解くベースのコードです
先に実行しておいてください
from collections import deque
import heapq
import random
import time

# 目標状態
GOAL_STATE = [
  [ 1,  2,  3,  4],
  [ 5,  6,  7,  8],
  [ 9, 10, 11, 12],
  [13, 14, 15,  0],
]

# 空白の移動方向
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_solvable(state):
    """スライドパズルが解けるかを判定"""
    rows, cols = len(state), len(state[0])
    
    # グリッドを1次元リストに変換（空白は無視）
    flat_list = [tile for row in state for tile in row if tile != 0]

    # 転倒数を計算
    inversions = sum(
        1 for i in range(len(flat_list)) for j in range(i + 1, len(flat_list)) if flat_list[i] > flat_list[j]
    )

    # 空白タイルの行（0インデックスで計算）
    blank_row = next(i for i, row in enumerate(state) if 0 in row)
    blank_row_from_bottom = rows - blank_row

    # 判定条件 (4x4の場合)
    if rows % 2 == 0:
        if inversions % 2 == 0 and blank_row_from_bottom % 2 == 1:
            return True
        elif inversions % 2 == 1 and blank_row_from_bottom % 2 == 0:
            return True
    else:
        if inversions % 2 == 0:
            return True
    return False

def find_blank(state):
  """空白セルの位置を見つける"""
  for i, row in enumerate(state):
      for j, val in enumerate(row):
          if val == 0:
              return i, j

def print_state(state):
    """
    パズルの状態をきれいに表示する
    :param state: 現在の状態 (2次元リスト)
    """
    for row in state:
        print(" ".join(f"{num:2}" if num != 0 else "  " for num in row))
    print()

def apply_solution(initial_state, solution):
    """
    初期状態に solution を適用し、各ステップ後の状態をプリント
    :param initial_state: 初期状態 (2次元リスト)
    :param solution: 解 (空白タイルの新しい位置を示すリスト)
    """
    state = [row[:] for row in initial_state]  # 初期状態をコピー
    rows, cols = len(state), len(state[0])

    # 空白タイル (0) の位置を見つける
    blank_pos = next((r, c) for r in range(rows) for c in range(cols) if state[r][c] == 0)

    print("Initial state:")
    print_state(state)

    # 解を適用
    for step, new_pos in enumerate(solution, start=1):
        # 現在の空白位置
        old_r, old_c = blank_pos
        new_r, new_c = new_pos

        # タイルをスワップ
        state[old_r][old_c], state[new_r][new_c] = state[new_r][new_c], state[old_r][old_c]

        # 更新された空白位置
        blank_pos = new_pos

        # 各ステップ後の状態をプリント
        print(f"After step {step}:")
        print_state(state)

これで準備は整いました
ここからはアルゴリズムの詳細を解説します。




幅優先探索 (BFS)


初期状態をキューに追加
キューから状態を1つ取り出し、目標状態と比較
解なら終了
探索済みならスキップ
空白セルを上下左右に動かして新しい状態を生成
新しい状態をキューに追加
キューが空になるか解が見つかるまで繰り返す


def bfs_solve(initial_state):
  """幅優先探索でスライドパズルを解く"""
  queue = deque([(initial_state, [], find_blank(initial_state))]) # 幅優先探索のキュー
  visited = set() # すでに探索済みの状態を記録する集合

  while queue:
      # state : 現在のパズルの状態
      # path: 現在までの移動履歴
      state, path, (blank_row, blank_col) = queue.popleft()
      if state == GOAL_STATE:
          return path  # 解が見つかったら手順を返す

      state_tuple = tuple(tuple(row) for row in state)
      if state_tuple in visited:
          continue
      visited.add(state_tuple)

      # DIRECTIONS : 空白セルを動かす4方向（上下左右）を表すリスト
      for dr, dc in DIRECTIONS:
          new_row, new_col = blank_row + dr, blank_col + dc
          if 0 <= new_row < 4 and 0 <= new_col < 4:
              new_state = [row[:] for row in state]
              new_state[blank_row][blank_col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_row][blank_col]
              queue.append((new_state, path + [(new_row, new_col)], (new_row, new_col)))



A* アルゴリズム


初期状態をヒープに追加
ヒープから評価値が最小の状態を取り出し、目標状態と比較
解なら移動履歴を返す
探索済みならスキップ
空白セルを上下左右に動かして新しい状態を生成
新しい状態をヒューリスティックで評価し、ヒープに追加
ヒープが空になるか解が見つかるまで繰り返す

# パズルの現在の状態と目標状態（GOAL_STATE）の間の「マンハッタン距離」を計算
def manhattan_distance(state):
    """マンハッタン距離を計算"""
    distance = 0
    for i in range(4):
        for j in range(4):
            val = state[i][j] # 現在の状態を参照
            if val != 0:
                target_row, target_col = divmod(val - 1, 4)
                distance += abs(target_row - i) + abs(target_col - j) # 現在位置（i, j）との差分
    return distance

def astar_solve(initial_state):
    """A*アルゴリズムでスライドパズルを解く"""
    open_set = [] # ヒープ（優先度付きキュー）で管理する探索候補リスト
    heapq.heappush(open_set, (manhattan_distance(initial_state), 0, initial_state, []))
    visited = set() # 探索済みの状態を管理する集合

    while open_set:
        _, cost, state, path = heapq.heappop(open_set) # 現在の状態を state、その手数を cost、移動履歴を path に代入
        if state == GOAL_STATE:
            return path  # 解が見つかったら手順を返す

        state_tuple = tuple(tuple(row) for row in state)
        if state_tuple in visited:
            continue
        visited.add(state_tuple)

        blank_row, blank_col = find_blank(state)
        for dr, dc in DIRECTIONS:
            new_row, new_col = blank_row + dr, blank_col + dc
            if 0 <= new_row < 4 and 0 <= new_col < 4:
                new_state = [row[:] for row in state]
                new_state[blank_row][blank_col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_row][blank_col]
                heapq.heappush(open_set, (cost + manhattan_distance(new_state), cost + 1, new_state, path + [(new_row, new_col)]))



IDA*アルゴリズム

初期状態の評価値（threshold）を計算
現在のしきい値内で深さ優先探索（DFS）を実行
解が見つかった場合は手順を返す
見つからない場合は次のしきい値を計算
次のしきい値で探索を再開
解が見つかるか探索が終了するまで繰り返す


def ida_star_solve(initial_state):
    """IDA*アルゴリズムでスライドパズルを解く"""
    def dfs(state, g, threshold, path, blank_pos):
        # 深さ優先探索を行い、指定されたコスト制限（threshold）内で解を探索
        f = g + manhattan_distance(state) # g : 現在までの手数（コスト）
        if f > threshold: # threshold :現在の探索制限（評価値の上限）
            return f, None
        if state == GOAL_STATE:
            return f, path # path : 現在までの移動履歴
        min_threshold = float('inf')
        blank_row, blank_col = blank_pos # blank_pos : 空白セルの位置
        for dr, dc in DIRECTIONS:
            new_row, new_col = blank_row + dr, blank_col + dc
            if 0 <= new_row < 4 and 0 <= new_col < 4:
                new_state = [row[:] for row in state]
                new_state[blank_row][blank_col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_row][blank_col]
                if len(path) > 0 and path[-1] == (new_row, new_col):
                    continue  # 直前の状態に戻るのを防ぐ
                t, result = dfs(new_state, g + 1, threshold, path + [(new_row, new_col)], (new_row, new_col))
                if result is not None:
                    return t, result
                min_threshold = min(min_threshold, t)
        return min_threshold, None

    threshold = manhattan_distance(initial_state) 
    blank_pos = find_blank(initial_state)
    path = []
    while True:
        t, result = dfs(initial_state, 0, threshold, path, blank_pos)
        if result is not None:
            return result
        if t == float('inf'):
            return None
        threshold = t



モンテカルロ探索

ランダムな移動を繰り返して解を探索
指定された最大試行回数（max_iterations）内に
目標状態（GOAL_STATE）に到達すれば
その移動手順（path）を返す
解が見つからない場合は None を返す


def monte_carlo_solve(initial_state, max_iterations=1000):
    """モンテカルロ探索でスライドパズルを解く"""
    state = [row[:] for row in initial_state] # 初期状態
    path = [] # 空白セル（0）の移動履歴を記録するリスト
    blank_row, blank_col = find_blank(state)

	# 最大 max_iterations 回、以下の操作を繰り返す
	# 現在の状態（state）が目標状態（GOAL_STATE）と一致した場合、成功として移動履歴（path）を返す
    for _ in range(max_iterations):
        if state == GOAL_STATE:
            return path  # 解が見つかったら終了

        # ランダムに移動
        valid_moves = [(dr, dc) for dr, dc in DIRECTIONS if 0 <= blank_row + dr < 4 and 0 <= blank_col + dc < 4]
        dr, dc = random.choice(valid_moves)
        new_row, new_col = blank_row + dr, blank_col + dc
        state[blank_row][blank_col], state[new_row][new_col] = state[new_row][new_col], state[blank_row][blank_col]
        path.append((new_row, new_col))
        blank_row, blank_col = new_row, new_col

    return None  # 最大試行回数を超えても解けなかった場合



4つのアルゴリズムでパズルを解く

solution が解けた状態です
コメントアウトして
アルゴリズムの違いを見る事ができます。

# 初期状態
initial_state = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 0, 11],
  [13, 14, 15, 12],
]

if is_solvable(initial_state):
    #solution = bfs_solve(initial_state)
    #solution = astar_solve(initial_state)
    #solution = ida_star_solve(initial_state)
    solution = monte_carlo_solve(initial_state)

    # 解を適用して各ステップ後の状態を表示
    apply_solution(initial_state, solution)
else:
    print("This puzzle is unsolvable.")
Initial state:
 1  2  3  4
 5  6  7  8
 9 10    11
13 14 15 12

After step 1:
 1  2  3  4
 5  6     8
 9 10  7 11
13 14 15 12

After step 2:
 1  2  3  4
 5  6  7  8
 9 10    11
13 14 15 12

After step 3:
 1  2  3  4
 5  6  7  8
 9 10 11   
13 14 15 12

After step 4:
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15   



まとめ

今回はスライドパズルを解く
4つのアルゴリズムを紹介しました

それぞれに特徴があり
まとめるとこんな感じです。

**アルゴリズム****計算量****メモリ消費****解の最適性**
幅優先探索 (BFS)\(O(b^d)\), b:分岐数, d:深さ高い最適解を保証
A\* アルゴリズム\(O(b^d)\)高い最適解を保証
IDA (反復深化 A)\(O(b^d)\)低い最適解を保証
モンテカルロ探索探索回数に依存低い保証されない


適用シナリオ

幅優先探索: 状態空間が小さく、メモリ制限が問題にならない場合
A*: 高精度のヒューリスティック関数を使い、効率的に最適解を探したい場合
IDA*: メモリ効率を優先しつつ、最適解を求める場合
モンテカルロ探索: 厳密な最適性が不要で、迅速におおよその解を得たい場合

アルゴリズムのよって
計算量やメモリの効率が異なってくるので
状況に応じた使い分けが必要になる事があります。

色々なアルゴリズムで
試してみてください。

それでは。
タグ ：
#プログラミング
#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}")


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

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


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

それでは


タグ ：
#プログラミング
#Python
#探索
#正方形
#長方形

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


解説動画はこちら



ステガノグラフィーとは


ステガノグラフィー（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




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

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

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



タグ ：
#python
#プログラミング
#ステガノグラフィー

このページのトップヘ