stackprobe7s_memo

何処にも披露する見込みの無いものを書き落とす場所

CsvFile*.cs

RDBを使わずにCSVでなんとかしてみた結果できた副産物。
特筆するようなところはないと思う。
概ね自分用。
　
CsvFileDBTable.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using Charlotte.Commons;
using Charlotte.Utilities;

namespace Charlotte.Tools
{
	public class CsvFileDBTable
	{
		// 制約：
		// -- 全ての行は1列以上の長さがなければならない。
		// -- 1列目は(重複ナシの)IDとする。
		// -- IDは空文字列不可

		// 注意：
		// -- 削除バッファ優先 -- 削除バッファ・追加または更新バッファ両方に同じIDがあった場合、削除として扱う。

		private static int BUFFER_SIZE_MAX = 1000;
		private static int MEMORY_LOAD_MAX = 50000000; // 50 MB

		public static void DEBUG_SetBufferSizeMax(int value)
		{
			BUFFER_SIZE_MAX = value;
		}

		public static void DEBUG_SetMemoryLoadMax(int value)
		{
			MEMORY_LOAD_MAX = value;
		}

		private static int RowsToMemoryLoad(string[][] rows)
		{
			return rows.Length * 100 + rows.Sum(row => row.Length * 100 + row.Sum(v => v.Length * 2)); // rough value
		}

		private static int RowToMemoryLoad(string[] row)
		{
			return RowsToMemoryLoad(new string[][] { row });
		}

		private string FilePath;

		/// <summary>
		/// 削除されたID
		/// 注意：バッファ内はID重複あり
		/// </summary>
		private string DeleteBufferFilePath
		{
			get
			{
				return this.FilePath + "_DeleteBuffer.csv";
			}
		}

		/// <summary>
		/// 追加または更新されたレコード
		/// 注意：バッファ内はID重複あり(後の方のレコードが有効)
		/// </summary>
		private string UpdateBufferFilePath
		{
			get
			{
				return this.FilePath + "_UpdateBuffer.csv";
			}
		}

		private int DeleteBufferSize;
		private int DeleteMemoryLoad;
		private int UpdateBufferSize;
		private int UpdateMemoryLoad;

		public CsvFileDBTable(string file)
		{
			this.FilePath = SCommon.MakeFullPath(file);

			// ----

			if (!File.Exists(this.FilePath))
				File.WriteAllBytes(this.FilePath, SCommon.EMPTY_BYTES);

			if (!File.Exists(this.DeleteBufferFilePath))
				File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);

			if (!File.Exists(this.UpdateBufferFilePath))
				File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);

			using (CsvFileReader reader = new CsvFileReader(this.DeleteBufferFilePath))
			{
				string[][] rows = reader.ReadToEnd();

				this.DeleteBufferSize = rows.Length;
				this.DeleteMemoryLoad = RowsToMemoryLoad(reader.ReadToEnd());
			}

			using (CsvFileReader reader = new CsvFileReader(this.UpdateBufferFilePath))
			{
				string[][] rows = reader.ReadToEnd();

				this.UpdateBufferSize = rows.Length;
				this.UpdateMemoryLoad = RowsToMemoryLoad(reader.ReadToEnd());
			}
		}

		/// <summary>
		/// 参照のみの全件走査
		/// 削除・更新を行う場合は FilterAll を使用すること。
		/// </summary>
		/// <param name="reaction">行リアクション</param>
		public void ForEach(Predicate<string[]> reaction)
		{
			if (reaction == null)
				throw new Exception("Bad reaction");

			HashSet<string> deletedOrKnownIDs = new HashSet<string>();
			string[][] addedOrUpdatedRows;

			using (CsvFileReader reader = new CsvFileReader(this.DeleteBufferFilePath))
			{
				foreach (string id in reader.ReadToEnd().Select(row => row[0]))
				{
					deletedOrKnownIDs.Add(id);
				}
			}

			using (CsvFileReader reader = new CsvFileReader(this.UpdateBufferFilePath))
			{
				addedOrUpdatedRows = reader.ReadToEnd();
			}

			foreach (string[] row in addedOrUpdatedRows.Reverse()) // 最後の更新を優先するため、最後から読み込む。
			{
				if (deletedOrKnownIDs.Contains(row[0]))
					continue;

				if (!reaction(row))
					return;

				deletedOrKnownIDs.Add(row[0]);
			}

			using (CsvFileReader reader = new CsvFileReader(this.FilePath))
			{
				for (; ; )
				{
					string[] row = reader.ReadRow();

					if (row == null)
						break;

					if (deletedOrKnownIDs.Contains(row[0]))
						continue;

					if (!reaction(row))
						break;
				}
			}
		}

		/// <summary>
		/// 削除・更新を伴う全件走査
		/// 行フィルタ：
		/// -- 何もしない場合 == 引数をそのまま返す。
		/// -- 更新する場合 == 新しい行を返す。-- 1列目(ID)を変更してはならない。
		/// -- 削除する場合 == nullを返す。
		/// </summary>
		/// <param name="filter">行フィルタ</param>
		public void FilterAll(Func<string[], string[]> filter)
		{
			if (filter == null)
				throw new Exception("Bad filter");

			using (WorkingDir wd = new WorkingDir())
			{
				string midFile = wd.MakePath();

				using (CsvFileWriter writer = new CsvFileWriter(midFile))
				{
					this.ForEach(row =>
					{
						string[] newRow = filter(row);

						if (newRow != null)
						{
							if (
								newRow.Length < 1 ||
								newRow.Any(v => v == null) ||
								newRow[0] != row[0] // 1列目(ID)の不一致
								)
								throw new Exception("Bad newRow");

							writer.WriteRow(newRow);
						}
						return true;
					});
				}

				SCommon.DeletePath(this.FilePath);
				File.Move(midFile, this.FilePath);
			}

			File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
			File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);

			this.DeleteBufferSize = 0;
			this.DeleteMemoryLoad = 0;
			this.UpdateBufferSize = 0;
			this.UpdateMemoryLoad = 0;
		}

		public List<string[]> Search(Predicate<string[]> match, int limit, out bool overflow)
		{
			if (
				match == null ||
				limit < 1 || SCommon.IMAX < limit
				)
				throw new Exception("Bad params");

			List<string[]> dest = new List<string[]>();
			bool wOverflow = false;

			this.ForEach(row =>
			{
				if (match(row)) // ? 検索対象
				{
					if (limit <= dest.Count)
					{
						wOverflow = true;
						return false;
					}
					dest.Add(row);
				}
				return true;
			});

			overflow = wOverflow;
			return dest;
		}

		public List<string[]> Search(Predicate<string[]> match, Comparison<string[]> comp, int limit, out int count)
		{
			if (
				match == null ||
				comp == null ||
				limit < 1 || SCommon.IMAX < limit
				)
				throw new Exception("Bad params");

			int DEST_MAX = Math.Max(limit + limit / 2, 100); // rough limit

			List<string[]> dest = new List<string[]>();
			int wCount = 0;

			this.ForEach(row =>
			{
				if (match(row)) // ? 検索対象
				{
					if (DEST_MAX < dest.Count)
					{
						dest.Sort(comp);
						dest.RemoveRange(limit, dest.Count - limit);
					}
					dest.Add(row);
					wCount++;
				}
				return true;
			});

			dest.Sort(comp);

			if (limit < dest.Count)
				dest.RemoveRange(limit, dest.Count - limit);

			count = wCount;
			return dest;
		}

		public List<string[]> Search(Predicate<string[]> match, Comparison<string[]> comp, int offset, int limit, out int count)
		{
			if (
				match == null ||
				comp == null ||
				offset < 0 || SCommon.IMAX < offset ||
				limit < 1 || SCommon.IMAX - offset < limit
				)
				throw new Exception("Bad params");

			List<string[]> dest = new List<string[]>();
			int wCount = 0;

			using (WorkingDir wd = new WorkingDir())
			{
				string midFile = wd.MakePath();

				using (CsvFileWriter writer = new CsvFileWriter(midFile))
				{
					this.ForEach(row =>
					{
						if (match(row)) // ? 検索対象
						{
							writer.WriteRow(row);
							wCount++;
						}
						return true;
					});
				}

				CsvFileSorter.Sort(midFile, comp);

				using (CsvFileReader reader = new CsvFileReader(midFile))
				{
					for (int index = 0; index < wCount; index++)
					{
						string[] row = reader.ReadRow();

						if (row == null)
							throw null; // never

						if (index < offset) // ? 出力開始位置の前
							continue;

						dest.Add(row);

						if (limit <= dest.Count) // ? 出力件数に達した。
							break;
					}
				}
			}

			count = wCount;
			return dest;
		}

		public void Search(Predicate<string[]> match, Comparison<string[]> comp, Predicate<string[]> reaction)
		{
			if (
				match == null ||
				comp == null ||
				reaction == null
				)
				throw new Exception("Bad params");

			using (WorkingDir wd = new WorkingDir())
			{
				string midFile = wd.MakePath();

				using (CsvFileWriter writer = new CsvFileWriter(midFile))
				{
					this.ForEach(row =>
					{
						if (match(row))
							writer.WriteRow(row);

						return true;
					});
				}

				CsvFileSorter.Sort(midFile, comp);

				using (CsvFileReader reader = new CsvFileReader(midFile))
				{
					for (; ; )
					{
						string[] row = reader.ReadRow();

						if (row == null)
							break;

						if (!reaction(row))
							break;
					}
				}
			}
		}

		/// <summary>
		/// 行の削除を行う。
		/// 大量の削除には向かない。
		/// 大量削除は FilterAll を検討すること。
		/// </summary>
		/// <param name="id">削除する行のID</param>
		public void Delete(string id)
		{
			if (string.IsNullOrEmpty(id))
				throw new Exception("Bad id");

			using (CsvFileWriter writer = new CsvFileWriter(this.DeleteBufferFilePath, true))
			{
				writer.WriteCell(id);
				writer.EndRow();
			}

			this.DeleteBufferSize += 1;
			this.DeleteMemoryLoad += RowToMemoryLoad(new string[] { id });

			if (
				BUFFER_SIZE_MAX < this.DeleteBufferSize ||
				MEMORY_LOAD_MAX < this.DeleteMemoryLoad
				)
				this.Flush();
		}

		/// <summary>
		/// 行の追加または更新を行う。
		/// 追加または更新された行は1行目の前に追加(移動)される。
		/// 大量の追加・更新には向かない。
		/// 大量追加は BulkInsert 大量更新は FilterAll を検討すること。
		/// </summary>
		/// <param name="row">追加または更新する行</param>
		public void AddOrUpdate(string[] row)
		{
			if (
				row == null ||
				row.Length < 1 || // 1列以上必要(1列目は(重複ナシの)ID)
				row.Any(v => v == null) ||
				row[0] == "" // IDは空文字列不可
				)
				throw new Exception("Bad row");

			if (1 <= this.DeleteBufferSize) // 削除バッファが優先であるため！
				this.Flush();

			using (CsvFileWriter writer = new CsvFileWriter(this.UpdateBufferFilePath, true))
			{
				writer.WriteRow(row);
			}

			this.UpdateBufferSize += 1;
			this.UpdateMemoryLoad += RowToMemoryLoad(row);

			if (
				BUFFER_SIZE_MAX < this.UpdateBufferSize ||
				MEMORY_LOAD_MAX < this.UpdateMemoryLoad
				)
				this.Flush();
		}

		private void Flush()
		{
			// ? バッファ無し -> フラッシュ不要
			if (
				this.DeleteBufferSize == 0 &&
				this.UpdateBufferSize == 0
				)
				return;

			using (WorkingDir wd = new WorkingDir())
			{
				string midFile = wd.MakePath();

				using (CsvFileWriter writer = new CsvFileWriter(midFile))
				{
					this.ForEach(row =>
					{
						writer.WriteRow(row);
						return true;
					});
				}

				SCommon.DeletePath(this.FilePath);
				File.Move(midFile, this.FilePath);
			}

			File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
			File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);

			this.DeleteBufferSize = 0;
			this.DeleteMemoryLoad = 0;
			this.UpdateBufferSize = 0;
			this.UpdateMemoryLoad = 0;
		}

		public void Sort(Comparison<string[]> comp)
		{
			if (comp == null)
				throw new Exception("Bad comp");

			this.Flush();
			CsvFileSorter.Sort(this.FilePath, comp);
		}

		public void Truncate()
		{
			File.WriteAllBytes(this.FilePath, SCommon.EMPTY_BYTES);
			File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
			File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);

			this.DeleteBufferSize = 0;
			this.DeleteMemoryLoad = 0;
			this.UpdateBufferSize = 0;
			this.UpdateMemoryLoad = 0;
		}

		public void BulkInsert(Func<string[]> reader)
		{
			if (reader == null)
				throw new Exception("Bad reader");

			this.Flush();

			using (CsvFileWriter writer = new CsvFileWriter(this.FilePath, true))
			{
				for (; ; )
				{
					string[] row = reader();

					if (row == null) // 読み込み終了
						break;

					// IDの重複はチェックしない。

					if (
						row.Length < 1 || // 1列以上必要(1列目は(重複ナシの)ID)
						row.Any(v => v == null) ||
						row[0] == "" // IDは空文字列不可
						)
						throw new Exception("Bad row");

					writer.WriteRow(row);
				}
			}
		}
	}
}

　
CsvFileSorter.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using Charlotte.Commons;
using Charlotte.Utilities;

namespace Charlotte.Tools
{
	public static class CsvFileSorter
	{
		private static int MEMORY_LOAD_MAX = 200000000; // 200 MB

		public static void DEBUG_SetMemoryLoadMax(int value)
		{
			MEMORY_LOAD_MAX = value;
		}

		public static List<int> DEBUG_LastRowCountList = new List<int>();

		private static int RowToMemoryLoad(string[] row)
		{
			return 100 + row.Length * 100 + row.Sum(v => v.Length) * 2; // rough value
		}

		public static void Sort(string file, Comparison<string[]> comp)
		{
			Sort(file, file, comp);
		}

		public static void Sort(string rFile, string wFile, Comparison<string[]> comp)
		{
			rFile = SCommon.MakeFullPath(rFile);
			wFile = SCommon.MakeFullPath(wFile);

			if (!File.Exists(rFile))
				throw new Exception("no rFile");

			if (Directory.Exists(wFile))
				throw new Exception("Bad wFile");

			if (comp == null)
				throw new Exception("Bad comp");

			using (WorkingDir wd = new WorkingDir())
			{
				Queue<string> q = new Queue<string>();

				DEBUG_LastRowCountList.Clear();

				using (CsvFileReader reader = new CsvFileReader(rFile))
				{
					for (; ; )
					{
						List<string[]> rows = new List<string[]>();
						string[] row;
						int memoryLoad = 0;

						for (; ; )
						{
							row = reader.ReadRow();

							if (row == null)
								break;

							rows.Add(row);
							memoryLoad += RowToMemoryLoad(row);

							if (MEMORY_LOAD_MAX < memoryLoad)
								break;
						}
						if (1 <= rows.Count)
						{
							rows.Sort(comp);

							string midFile = wd.MakePath();

							using (CsvFileWriter writer = new CsvFileWriter(midFile))
							{
								writer.WriteRows(rows);
							}
							q.Enqueue(midFile);

							DEBUG_LastRowCountList.Add(rows.Count);
						}
						if (row == null)
							break;
					}
				}

				if (q.Count == 0)
				{
					File.WriteAllBytes(wFile, SCommon.EMPTY_BYTES);
				}
				else
				{
					while (2 <= q.Count)
					{
						string midFile1 = q.Dequeue();
						string midFile2 = q.Dequeue();
						string midFile3 = wd.MakePath();

						using (CsvFileReader reader1 = new CsvFileReader(midFile1))
						using (CsvFileReader reader2 = new CsvFileReader(midFile2))
						using (CsvFileWriter writer = new CsvFileWriter(midFile3))
						{
							string[] row1 = reader1.ReadRow();
							string[] row2 = reader2.ReadRow();

							while (row1 != null && row2 != null)
							{
								int ret = comp(row1, row2);

								if (ret <= 0)
								{
									writer.WriteRow(row1);
									row1 = reader1.ReadRow();
								}
								if (0 <= ret)
								{
									writer.WriteRow(row2);
									row2 = reader2.ReadRow();
								}
							}
							while (row1 != null)
							{
								writer.WriteRow(row1);
								row1 = reader1.ReadRow();
							}
							while (row2 != null)
							{
								writer.WriteRow(row2);
								row2 = reader2.ReadRow();
							}
						}
						q.Enqueue(midFile3);
					}
					SCommon.DeletePath(wFile);
					File.Move(q.Dequeue(), wFile);
				}
			}
		}
	}
}

　
CsvFileReader.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using Charlotte.Commons;

namespace Charlotte.Utilities
{
	public class CsvFileReader : IDisposable
	{
		public const char DELIMITER_COMMA = ','; // for .csv
		public const char DELIMITER_SPACE = ' '; // for .ssv
		public const char DELIMITER_TAB = '\t';  // for .tsv

		private char Delimiter;
		private StreamReader Reader;

		public CsvFileReader(string file)
			: this(file, SCommon.ENCODING_SJIS)
		{ }

		public CsvFileReader(string file, Encoding encoding)
			: this(file, encoding, DELIMITER_COMMA)
		{ }

		public CsvFileReader(string file, Encoding encoding, char delimiter)
		{
			this.Delimiter = delimiter;
			this.Reader = new StreamReader(file, encoding);
		}

		private int LastChar;

		private int ReadChar()
		{
			do
			{
				this.LastChar = this.Reader.Read();
			}
			while (this.LastChar == '\r');

			return this.LastChar;
		}

		private bool EnclosedCell;

		private string ReadCell()
		{
			StringBuilder buff = new StringBuilder();

			if (this.ReadChar() == '"')
			{
				while (this.ReadChar() != -1 && (this.LastChar != '"' || this.ReadChar() == '"'))
				{
					buff.Append((char)this.LastChar);
				}
				this.EnclosedCell = true;
			}
			else
			{
				while (this.LastChar != -1 && this.LastChar != '\n' && this.LastChar != this.Delimiter)
				{
					buff.Append((char)this.LastChar);
					this.ReadChar();
				}
				this.EnclosedCell = false;
			}
			return buff.ToString();
		}

		public string[] ReadRow()
		{
			List<string> row = new List<string>();

			do
			{
				row.Add(this.ReadCell());
			}
			while (this.LastChar != -1 && this.LastChar != '\n');

			if (this.LastChar == -1 && row.Count == 1 && row[0] == "" && !this.EnclosedCell)
				return null;

			return row.ToArray();
		}

		public string[][] ReadToEnd()
		{
			List<string[]> rows = new List<string[]>();

			for (; ; )
			{
				string[] row = this.ReadRow();

				if (row == null)
					break;

				rows.Add(row);
			}
			return rows.ToArray();
		}

		public void Dispose()
		{
			if (this.Reader != null)
			{
				this.Reader.Dispose();
				this.Reader = null;
			}
		}
	}
}

　
CsvFileWriter.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using Charlotte.Commons;

namespace Charlotte.Utilities
{
	public class CsvFileWriter : IDisposable
	{
		public const char DELIMITER_COMMA = ','; // for .csv
		public const char DELIMITER_SPACE = ' '; // for .ssv
		public const char DELIMITER_TAB = '\t';  // for .tsv

		private char Delimiter;
		private StreamWriter Writer;

		public CsvFileWriter(string file, bool append = false)
			: this(file, append, SCommon.ENCODING_SJIS)
		{ }

		public CsvFileWriter(string file, bool append, Encoding encoding)
			: this(file, append, encoding, DELIMITER_COMMA)
		{ }

		public CsvFileWriter(string file, bool append, Encoding encoding, char delimiter)
		{
			this.Delimiter = delimiter;
			this.Writer = new StreamWriter(file, append, encoding);
		}

		/// <summary>
		/// 次に書き込むセルが行の最初のセルか
		/// </summary>
		private bool FirstCell = true;

		public void WriteCell(string cell)
		{
			if (this.FirstCell)
				this.FirstCell = false;
			else
				this.Writer.Write(this.Delimiter);

			if (
				cell.Contains('"') ||
				cell.Contains('\n') ||
				cell.Contains(this.Delimiter)
				)
			{
				this.Writer.Write('"');
				this.Writer.Write(cell.Replace("\"", "\"\""));
				this.Writer.Write('"');
			}
			else
			{
				this.Writer.Write(cell);
			}
		}

		public void EndRow()
		{
			this.Writer.Write('\n');
			this.FirstCell = true;
		}

		public void WriteCells(IList<string> cells)
		{
			foreach (string cell in cells)
			{
				this.WriteCell(cell);
			}
		}

		public void WriteRow(IList<string> row)
		{
			foreach (string cell in row)
			{
				this.WriteCell(cell);
			}
			this.EndRow();
		}

		public void WriteRows(IList<string[]> rows)
		{
			foreach (string[] row in rows)
			{
				this.WriteRow(row);
			}
		}

		public void Dispose()
		{
			if (this.Writer != null)
			{
				this.Writer.Dispose();
				this.Writer = null;
			}
		}
	}
}

フィッシャー・イェーツのシャッフル

長さ N の配列 arr = [ 0, 1, 2, ... (N-1) ] をシャッフルしたとき、どの要素から c = arr[c]; というように辿っていっても巡回する。
　
source:

function Shuffle(arr) {
    for (let i = arr.length - 1; 0 < i; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        let wk = arr[i];
        arr[i] = arr[j];
        arr[j] = wk;
    }
}

function ShowRings(arr) {
    let b = Array(arr.length).fill(true);
    for (let i = 0; i < arr.length; i++) {
        if (b[i]) {
            let c = i;
            let a = [];
            do {
                a.push(c);
                b[c] = false;
                c = arr[c];
            }
            while (c != i);
            
            let s = "+--> " + a.join(" --> ") + " --+";
            console.log(s);
            console.log("|" + " ".repeat(s.length - 2) + "|");
            console.log("+" + "-".repeat(s.length - 2) + "+");
            console.log();
        }
    }
}

let N = 30;
let arr = [...Array(N).keys()];

Shuffle(arr);

console.log("[ " + arr.join(", ") + " ]");
console.log();

ShowRings(arr);

outputs:

[ 4, 10, 19, 13, 8, 6, 12, 29, 17, 26, 28, 21, 1, 18, 0, 23, 27, 15, 7, 9, 2, 24, 22, 3, 20, 11, 16, 25, 5, 14 ]

+--> 0 --> 4 --> 8 --> 17 --> 15 --> 23 --> 3 --> 13 --> 18 --> 7 --> 29 --> 14 --+
|                                                                                 |
+---------------------------------------------------------------------------------+

+--> 1 --> 10 --> 28 --> 5 --> 6 --> 12 --+
|                                         |
+-----------------------------------------+

+--> 2 --> 19 --> 9 --> 26 --> 16 --> 27 --> 25 --> 11 --> 21 --> 24 --> 20 --+
|                                                                             |
+-----------------------------------------------------------------------------+

+--> 22 --+
|         |
+---------+
[ 20, 28, 13, 17, 6, 1, 14, 7, 26, 27, 12, 4, 23, 2, 22, 15, 5, 19, 24, 11, 21, 10, 29, 3, 8, 18, 16, 9, 25, 0 ]

+--> 0 --> 20 --> 21 --> 10 --> 12 --> 23 --> 3 --> 17 --> 19 --> 11 --> 4 --> 6 --> 14 --> 22 --> 29 --+
|                                                                                                       |
+-------------------------------------------------------------------------------------------------------+

+--> 1 --> 28 --> 25 --> 18 --> 24 --> 8 --> 26 --> 16 --> 5 --+
|                                                              |
+--------------------------------------------------------------+

+--> 2 --> 13 --+
|               |
+---------------+

+--> 7 --+
|        |
+--------+

+--> 9 --> 27 --+
|               |
+---------------+

+--> 15 --+
|         |
+---------+
[ 5, 2, 12, 13, 16, 29, 28, 14, 9, 6, 24, 20, 3, 19, 4, 11, 21, 22, 8, 26, 25, 1, 23, 27, 10, 0, 18, 15, 7, 17 ]

+--> 0 --> 5 --> 29 --> 17 --> 22 --> 23 --> 27 --> 15 --> 11 --> 20 --> 25 --+
|                                                                             |
+-----------------------------------------------------------------------------+

+--> 1 --> 2 --> 12 --> 3 --> 13 --> 19 --> 26 --> 18 --> 8 --> 9 --> 6 --> 28 --> 7 --> 14 --> 4 --> 16 --> 21 --+
|                                                                                                                 |
+-----------------------------------------------------------------------------------------------------------------+

+--> 10 --> 24 --+
|                |
+----------------+

　
...となるのですが、シャッフルをちょっとだけ変えると

<<<        let j = Math.floor(Math.random() * (i + 1));
>>>        let j = Math.floor(Math.random() * i);

source:

function Shuffle(arr) {
    for (let i = arr.length - 1; 0 < i; i--) {
        let j = Math.floor(Math.random() * i);
        let wk = arr[i];
        arr[i] = arr[j];
        arr[j] = wk;
    }
}

function ShowRings(arr) {
    let b = Array(arr.length).fill(true);
    for (let i = 0; i < arr.length; i++) {
        if (b[i]) {
            let c = i;
            let a = [];
            do {
                a.push(c);
                b[c] = false;
                c = arr[c];
            }
            while (c != i);
            
            let s = "+--> " + a.join(" --> ") + " --+";
            console.log(s);
            console.log("|" + " ".repeat(s.length - 2) + "|");
            console.log("+" + "-".repeat(s.length - 2) + "+");
            console.log();
        }
    }
}

let N = 30;
let arr = [...Array(N).keys()];

Shuffle(arr);

console.log("[ " + arr.join(", ") + " ]");
console.log();

ShowRings(arr);

outputs:

[ 5, 25, 23, 4, 22, 12, 8, 9, 26, 19, 14, 10, 29, 27, 6, 21, 13, 11, 24, 28, 1, 16, 0, 17, 15, 7, 3, 20, 2, 18 ]

+--> 0 --> 5 --> 12 --> 29 --> 18 --> 24 --> 15 --> 21 --> 16 --> 13 --> 27 --> 20 --> 1 --> 25 --> 7 --> 9 --> 19 --> 28 --> 2 --> 23 --> 17 --> 11 --> 10 --> 14 --> 6 --> 8 --> 26 --> 3 --> 4 --> 22 --+
|                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
[ 25, 11, 28, 6, 17, 1, 13, 19, 18, 12, 15, 10, 26, 20, 22, 23, 14, 24, 0, 21, 27, 3, 9, 29, 5, 4, 2, 8, 7, 16 ]

+--> 0 --> 25 --> 4 --> 17 --> 24 --> 5 --> 1 --> 11 --> 10 --> 15 --> 23 --> 29 --> 16 --> 14 --> 22 --> 9 --> 12 --> 26 --> 2 --> 28 --> 7 --> 19 --> 21 --> 3 --> 6 --> 13 --> 20 --> 27 --> 8 --> 18 --+
|                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
[ 7, 28, 8, 22, 24, 0, 5, 16, 29, 25, 21, 10, 27, 12, 13, 2, 17, 23, 26, 9, 15, 3, 4, 11, 20, 1, 14, 6, 18, 19 ]

+--> 0 --> 7 --> 16 --> 17 --> 23 --> 11 --> 10 --> 21 --> 3 --> 22 --> 4 --> 24 --> 20 --> 15 --> 2 --> 8 --> 29 --> 19 --> 9 --> 25 --> 1 --> 28 --> 18 --> 26 --> 14 --> 13 --> 12 --> 27 --> 6 --> 5 --+
|                                                                                                                                                                                                          |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

というように、ひとつの輪(円順列？)になる。
このアルゴリズムなんていうのかしら...

奥沢は目黒区だと勘違いしていた話 (C# + 国土地理院の地図データ)

つい最近(と言っても数年前)まで東急目黒線の奥沢駅は目黒区か大田区だと思っていたのですが、ひょんなきっかけで世田谷区だと知りました。
まぁ勝手に思い込んでいただけだったので多少驚いて素直に納得したのですが、むしろ何十年もそのことに気づかなかったという方が不思議というか驚きだったわけです。
で、何でそんな勘違いをしていたかという小ネタをやるために国土地理院の地図データをちょっとだけ触ってみようかと思います。


国土地理院が全国の地図データを公開していて、利用規約や制限などはありますが割と詳細な地図データが無料で手に入ります。
　
fgd.gsi.go.jp
　
ダウンロード ⇒ 基盤地図情報 基本項目 ⇒ ファイル選択へ
と進んで行き、今回必要なメッシュ 533935 のみダウンロードします。

ダウンロードした FG-GML-533935-ALL-20221001.zip を展開すると

FG-GML-533935-AdmArea-20221001-0001.xml
FG-GML-533935-AdmBdry-20221001-0001.xml
FG-GML-533935-AdmPt-20221001-0001.xml
FG-GML-533935-BldA-20221001-0001.xml
FG-GML-533935-BldA-20221001-0002.xml
FG-GML-533935-BldA-20221001-0003.xml
FG-GML-533935-BldA-20221001-0004.xml
FG-GML-533935-BldL-20221001-0001.xml
FG-GML-533935-Cntr-20221001-0001.xml
FG-GML-533935-CommBdry-20221001-0001.xml
FG-GML-533935-CommPt-20221001-0001.xml
FG-GML-533935-Cstline-20221001-0001.xml
FG-GML-533935-ElevPt-20221001-0001.xml
FG-GML-533935-GCP-20221001-0001.xml
FG-GML-533935-RailCL-20221001-0001.xml
FG-GML-533935-RdCompt-20221001-0001.xml
FG-GML-533935-RdEdg-20221001-0001.xml
FG-GML-533935-SBAPt-20221001-0001.xml
FG-GML-533935-SBBdry-20221001-0001.xml
FG-GML-533935-WA-20221001-0001.xml
FG-GML-533935-WL-20221001-0001.xml
FG-GML-533935-WStrA-20221001-0001.xml
FG-GML-533935-WStrL-20221001-0001.xml
fmdid22-1001.xml

ファイル命名規則：https://www.gsi.go.jp/common/000093391.pdf

といろいろ入っていますが、ダウンロードページにある FGDV というビューアで確認した上で今回必要なファイルを抜き出すと...

ファイル 内容
FG-GML-533935-AdmArea-20221001-0001.xml 行政区画
FG-GML-533935-BldL-20221001-0001.xml 建築物の外周線
FG-GML-533935-RailCL-20221001-0001.xml (鉄道の)軌道の中心線
FG-GML-533935-RdEdg-20221001-0001.xml 道路

...となるので、これらのファイルだけ見ていきます。
　
先ずそこそこファイルがでかいので私のショボいPCで読み込めるのか確認します。

public void Test01()
{
	LoadXMLTest(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-AdmArea-20221001-0001.xml");
	LoadXMLTest(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-BldL-20221001-0001.xml");
	LoadXMLTest(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RailCL-20221001-0001.xml");
	LoadXMLTest(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RdEdg-20221001-0001.xml");
}

private List<XMLNode> LoadedXMLs = new List<XMLNode>();

private void LoadXMLTest(string file)
{
	Console.WriteLine("Load " + file);
	DateTime stTm = DateTime.Now;
	LoadedXMLs.Add(XMLNode.LoadFromFile(file));
	DateTime edTm = DateTime.Now;
	Console.WriteLine("OK " + (edTm - stTm).TotalSeconds.ToString("F3") + "s");
}

Output

Load C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-AdmArea-20221001-0001.xml
OK 0.016s
Load C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-BldL-20221001-0001.xml
OK 9.249s
Load C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RailCL-20221001-0001.xml
OK 0.094s
Load C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RdEdg-20221001-0001.xml
OK 2.085s

読めました。
建築物の外周線はでかいだけあって重い。PCがショボいってのもあるけど・・・。
　
続いてフォーマットの確認。
昔この辺のファイルを触った記憶があるのだけど、もう詳細は忘れました。
どこかに書式に関する説明があるだろうしそれを読むべきだろうけど、ぱっと見それほど複雑ではなさそうなので強引にデータを読み解くことにします。

public void Test02()
{
	PrintXMLPaths(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-AdmArea-20221001-0001.xml");
	PrintXMLPaths(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-BldL-20221001-0001.xml");
	PrintXMLPaths(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RailCL-20221001-0001.xml");
	PrintXMLPaths(@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RdEdg-20221001-0001.xml");
}

private void PrintXMLPaths(string file)
{
	HashSet<string> xmlPaths = new HashSet<string>();
	XMLNode root = XMLNode.LoadFromFile(file);
	root.Search((xmlPath, node) => xmlPaths.Add(xmlPath));

	Console.WriteLine(file);
	Console.WriteLine();

	List<string> lines = new List<string>();

	lines.Add("XMLパス*最小の個数*最大の個数");
	lines.Add("----");

	foreach (string xmlPath in xmlPaths.OrderBy(SCommon.Comp))
		lines.Add(xmlPath
			+ "*" + GetNodeCount(root, xmlPath, int.MaxValue, Math.Min)
			+ "*" + GetNodeCount(root, xmlPath, int.MinValue, Math.Max));

	Common.ToConsoleTable(lines);

	foreach (string line in lines)
		Console.WriteLine(line);

	Console.WriteLine();
}

private int GetNodeCount(XMLNode root, string xmlPath, int count, Func<int, int, int> chooser)
{
	int p = xmlPath.LastIndexOf('/');

	if (p == -1) // ? ルートTag
		return 1;

	string parentXmlPath = xmlPath.Substring(0, p);
	string name = xmlPath.Substring(p + 1);

	root.Search((xp, node) =>
	{
		if (xp == parentXmlPath)
			count = chooser(count, node.Children.Where(n => n.Name == name).Count());

		return true;
	});

	return count;
}

Output

C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-AdmArea-20221001-0001.xml

XMLパス                                                                                                               最小の個数  最大の個数
--------------------------------------------------------------------------------------------------------------------------------------------
Dataset                                                                                                               1           1
Dataset/AdmArea                                                                                                       14          14
Dataset/AdmArea/admCode                                                                                               1           1
Dataset/AdmArea/area                                                                                                  1           1
Dataset/AdmArea/area/Surface                                                                                          1           1
Dataset/AdmArea/area/Surface/id                                                                                       1           1
Dataset/AdmArea/area/Surface/patches                                                                                  1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch                                                                     1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior                                                            1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring                                                       1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember                                           1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember/Curve                                     1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember/Curve/id                                  1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember/Curve/segments                            1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember/Curve/segments/LineStringSegment          1           1
Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember/Curve/segments/LineStringSegment/posList  1           1
Dataset/AdmArea/area/Surface/srsName                                                                                  1           1
Dataset/AdmArea/devDate                                                                                               1           1
Dataset/AdmArea/devDate/id                                                                                            1           1
Dataset/AdmArea/devDate/timePosition                                                                                  1           1
Dataset/AdmArea/fid                                                                                                   1           1
Dataset/AdmArea/id                                                                                                    1           1
Dataset/AdmArea/lfSpanFr                                                                                              1           1
Dataset/AdmArea/lfSpanFr/id                                                                                           1           1
Dataset/AdmArea/lfSpanFr/timePosition                                                                                 1           1
Dataset/AdmArea/name                                                                                                  1           1
Dataset/AdmArea/orgGILvl                                                                                              1           1
Dataset/AdmArea/type                                                                                                  1           1
Dataset/AdmArea/vis                                                                                                   1           1
Dataset/description                                                                                                   1           1
Dataset/gml                                                                                                           1           1
Dataset/id                                                                                                            1           1
Dataset/name                                                                                                          1           1
Dataset/schemaLocation                                                                                                1           1
Dataset/xlink                                                                                                         1           1
Dataset/xmlns                                                                                                         1           1
Dataset/xsi                                                                                                           1           1

C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-BldL-20221001-0001.xml

XMLパス                                                    最小の個数  最大の個数
---------------------------------------------------------------------------------
Dataset                                                    1           1
Dataset/BldL                                               384932      384932
Dataset/BldL/devDate                                       1           1
Dataset/BldL/devDate/id                                    1           1
Dataset/BldL/devDate/timePosition                          1           1
Dataset/BldL/fid                                           1           1
Dataset/BldL/id                                            1           1
Dataset/BldL/lfSpanFr                                      1           1
Dataset/BldL/lfSpanFr/id                                   1           1
Dataset/BldL/lfSpanFr/timePosition                         1           1
Dataset/BldL/loc                                           1           1
Dataset/BldL/loc/Curve                                     1           1
Dataset/BldL/loc/Curve/id                                  1           1
Dataset/BldL/loc/Curve/segments                            1           1
Dataset/BldL/loc/Curve/segments/LineStringSegment          1           1
Dataset/BldL/loc/Curve/segments/LineStringSegment/posList  1           1
Dataset/BldL/loc/Curve/srsName                             1           1
Dataset/BldL/orgGILvl                                      1           1
Dataset/BldL/type                                          1           1
Dataset/description                                        1           1
Dataset/gml                                                1           1
Dataset/id                                                 1           1
Dataset/name                                               1           1
Dataset/schemaLocation                                     1           1
Dataset/xlink                                              1           1
Dataset/xmlns                                              1           1
Dataset/xsi                                                1           1

C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RailCL-20221001-0001.xml

XMLパス                                                      最小の個数  最大の個数
-----------------------------------------------------------------------------------
Dataset                                                      1           1
Dataset/RailCL                                               3910        3910
Dataset/RailCL/devDate                                       1           1
Dataset/RailCL/devDate/id                                    1           1
Dataset/RailCL/devDate/timePosition                          1           1
Dataset/RailCL/fid                                           1           1
Dataset/RailCL/id                                            1           1
Dataset/RailCL/lfSpanFr                                      1           1
Dataset/RailCL/lfSpanFr/id                                   1           1
Dataset/RailCL/lfSpanFr/timePosition                         1           1
Dataset/RailCL/loc                                           1           1
Dataset/RailCL/loc/Curve                                     1           1
Dataset/RailCL/loc/Curve/id                                  1           1
Dataset/RailCL/loc/Curve/segments                            1           1
Dataset/RailCL/loc/Curve/segments/LineStringSegment          1           1
Dataset/RailCL/loc/Curve/segments/LineStringSegment/posList  1           1
Dataset/RailCL/loc/Curve/srsName                             1           1
Dataset/RailCL/orgGILvl                                      1           1
Dataset/RailCL/type                                          1           1
Dataset/RailCL/vis                                           1           1
Dataset/description                                          1           1
Dataset/gml                                                  1           1
Dataset/id                                                   1           1
Dataset/name                                                 1           1
Dataset/schemaLocation                                       1           1
Dataset/xlink                                                1           1
Dataset/xmlns                                                1           1
Dataset/xsi                                                  1           1

C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RdEdg-20221001-0001.xml

XMLパス                                                     最小の個数  最大の個数
----------------------------------------------------------------------------------
Dataset                                                     1           1
Dataset/RdEdg                                               46633       46633
Dataset/RdEdg/admOffice                                     1           1
Dataset/RdEdg/devDate                                       1           1
Dataset/RdEdg/devDate/id                                    1           1
Dataset/RdEdg/devDate/timePosition                          1           1
Dataset/RdEdg/fid                                           1           1
Dataset/RdEdg/id                                            1           1
Dataset/RdEdg/lfSpanFr                                      1           1
Dataset/RdEdg/lfSpanFr/id                                   1           1
Dataset/RdEdg/lfSpanFr/timePosition                         1           1
Dataset/RdEdg/loc                                           1           1
Dataset/RdEdg/loc/Curve                                     1           1
Dataset/RdEdg/loc/Curve/id                                  1           1
Dataset/RdEdg/loc/Curve/segments                            1           1
Dataset/RdEdg/loc/Curve/segments/LineStringSegment          1           1
Dataset/RdEdg/loc/Curve/segments/LineStringSegment/posList  1           1
Dataset/RdEdg/loc/Curve/srsName                             1           1
Dataset/RdEdg/orgGILvl                                      1           1
Dataset/RdEdg/type                                          1           1
Dataset/RdEdg/vis                                           1           1
Dataset/description                                         1           1
Dataset/gml                                                 1           1
Dataset/id                                                  1           1
Dataset/name                                                1           1
Dataset/schemaLocation                                      1           1
Dataset/xlink                                               1           1
Dataset/xmlns                                               1           1
Dataset/xsi                                                 1           1

ぱっと見の予想どおりシンプルな構造でした。
posList というタグにポリゴン (緯度・軽度の組み合わせのリスト) が入っているようなので、とりあえず抽出してみます。
行政区画には行政区名 (/Dataset/AdmArea/name) が入っているけど、建物名・路線名は入っていない模様。
なので線だけで何とかしてみます。

public void Test03()
{
	ExportPosList(
		@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-AdmArea-20221001-0001.xml",
		@"C:\temp\Area.txt",
		"Dataset/AdmArea/area/Surface/patches/PolygonPatch/exterior/Ring/curveMember/Curve/segments/LineStringSegment/posList"
		);
	ExportPosList(
		@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-BldL-20221001-0001.xml",
		@"C:\temp\Building.txt",
		"Dataset/BldL/loc/Curve/segments/LineStringSegment/posList"
		);
	ExportPosList(
		@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RailCL-20221001-0001.xml",
		@"C:\temp\Rail.txt",
		"Dataset/RailCL/loc/Curve/segments/LineStringSegment/posList"
		);
	ExportPosList(
		@"C:\temp\FG-GML-533935-ALL-20221001\FG-GML-533935-RdEdg-20221001-0001.xml",
		@"C:\temp\Road.txt",
		"Dataset/RdEdg/loc/Curve/segments/LineStringSegment/posList"
		);
}

private void ExportPosList(string mapFile, string polyFile, string polyXmlPath)
{
	XMLNode root = XMLNode.LoadFromFile(mapFile);

	using (StreamWriter writer = new StreamWriter(polyFile, false, Encoding.ASCII))
	{
		root.Search((xmlPath, node) =>
		{
			if (xmlPath == polyXmlPath)
			{
				writer.WriteLine(node.Value);
				writer.WriteLine(); // 空行 -- データの区切りとして
			}
			return true;
		});
	}
}

C:\temp\Area.txt , C:\temp\Building.txt , C:\temp\Rail.txt , C:\temp\Road.txt が作成されます。
中身は↓こんな感じです。

Building.txt
35.584445222 139.628468000
35.584447750 139.628575778
35.584368250 139.628578528
35.584365722 139.628470833
35.584445222 139.628468000

35.588461500 139.628454222
35.588464944 139.628520750
35.588304417 139.628533194
35.588301444 139.628475944
35.588307222 139.628475472
35.588306750 139.628466222
35.588461500 139.628454222

35.585365083 139.628463556
35.585365944 139.628491694
35.585374139 139.628491222
35.585375750 139.628545833
35.585312750 139.628548528
35.585310278 139.628466000
35.585365083 139.628463556
...

　
続いてこのデータの表示(画像ファイルへの変換)を試みます。
表示範囲としては以下の駅が入っていればよい想定です。(緯度経度は Wikipedia から)

場所 緯度 経度
九品仏駅 35.605417 139.661000
自由が丘駅 35.607500 139.668889
緑ヶ丘駅 35.606389 139.679361
大岡山駅 35.607500 139.685639
田園調布駅 35.596889 139.667306
奥沢駅 35.603833 139.672306

緯度経度を距離に変換することを考えます。

地球は楕円体なのですが、Wikipedia によると
赤道面での直径 12756.274 km (半径 6378.137 km)
極半径 6356.752 km
と、ほとんど変わらないので平均をとって半径 6367.4445 km の球として考えます。

表示範囲はだいたい北緯 35.6 度付近なので、経度については北緯 35.6 度における東西方向一周の長さから換算します。

double ER = 6367444.5; // 地球の半径(meter)
double LAT = 35.6; // 基準とする北緯(degree)

double latToMeter = ER * Math.PI / 180.0;
double lonToMeter = ER * Math.Cos(LAT * Math.PI / 180.0) * Math.PI / 180.0;

Console.WriteLine("緯度の 1 度を " + latToMeter.ToString("F9") + " メートルとする。");
Console.WriteLine("経度の 1 度を " + lonToMeter.ToString("F9") + " メートルとする。");

Output

緯度の 1 度を 111132.871463004 メートルとする。
経度の 1 度を 90362.222363910 メートルとする。

　
以上を踏まえて画像への変換を行います。

public void Test05()
{
	// 表示範囲(緯度経度)
	double NORTH_LAT = 35.607500; // 自由が丘駅
	double SOUTH_LAT = 35.596889; // 田園調布駅
	double WEST_LON = 139.661000; // 九品仏駅
	double EAST_LON = 139.685639; // 大岡山駅

	// 表示範囲のマージン(meter)
	double MARGIN = 300.0;

	// 出力画像の幅(pixel)
	int IMAGE_WIDTH = 1600;

	OutputImage(NORTH_LAT, SOUTH_LAT, WEST_LON, EAST_LON, MARGIN, IMAGE_WIDTH);
}

private void OutputImage(double nLat, double sLat, double wLon, double eLon, double margin, int imageWidth)
{
	double LAT_TO_METER = 111132.871463004;
	double LON_TO_METER = 90362.222363910;

	// マージン適用
	{
		nLat += margin / LAT_TO_METER;
		sLat -= margin / LAT_TO_METER;
		wLon -= margin / LON_TO_METER;
		eLon += margin / LON_TO_METER;
	}

	double xLon = eLon - wLon;
	double yLat = nLat - sLat;

	double xMeter = xLon * LON_TO_METER;
	double yMeter = yLat * LAT_TO_METER;

	double meterToPixel = imageWidth / xMeter;

	double latToPixel = LAT_TO_METER * meterToPixel;
	double lonToPixel = LON_TO_METER * meterToPixel;

	int w = imageWidth;
	int h = SCommon.ToInt(yMeter * meterToPixel);

	Bitmap image = new Bitmap(w, h);

	using (Graphics g = Graphics.FromImage(image))
	{
		g.FillRectangle(new SolidBrush(Color.White), 0, 0, w, h);

		Action<string, Pen> drawPolyFromFile = (polyFile, pen) =>
		{
			string[] polyLines = File.ReadAllLines(polyFile, Encoding.ASCII);
			int polyLineIndex = 0;

			while (polyLineIndex < polyLines.Length)
			{
				List<double[]> poly = new List<double[]>();

				while (polyLines[polyLineIndex] != "")
					poly.Add(polyLines[polyLineIndex++].Split(' ').Select(v => double.Parse(v)).ToArray());

				polyLineIndex++;

				foreach (double[] p in poly)
				{
					p[0] = (nLat - p[0]) * latToPixel; // Lat to pixel
					p[1] = (p[1] - wLon) * lonToPixel; // Lon to pixel
				}

				for (int polyIndex = 0; polyIndex + 1 < poly.Count; polyIndex++)
				{
					double[] p = poly[polyIndex + 0];
					double[] q = poly[polyIndex + 1];

					if (
						(0.0 <= p[0] && p[0] < h) ||
						(0.0 <= p[1] && p[1] < w) ||
						(0.0 <= q[0] && q[0] < h) ||
						(0.0 <= q[1] && q[1] < w)
						)
					{
						g.DrawLine(pen, (float)p[1], (float)p[0], (float)q[1], (float)q[0]);
					}
				}
			}
		};

		drawPolyFromFile(
			@"C:\temp\Building.txt",
			new Pen(new SolidBrush(Color.FromArgb(128, 255, 128)), 1.0F)
			);
		drawPolyFromFile(
			@"C:\temp\Road.txt",
			new Pen(new SolidBrush(Color.FromArgb(128, 128, 128)), 1.0F)
			);
		drawPolyFromFile(
			@"C:\temp\Rail.txt",
			new Pen(new SolidBrush(Color.FromArgb(0, 0, 0)), 1.0F)
			);
		drawPolyFromFile(
			@"C:\temp\Area.txt",
			new Pen(new SolidBrush(Color.FromArgb(64, 255, 0, 0)), 5.0F)
			);
	}
	image.Save(SCommon.NextOutputPath() + ".png");
}

Output

奥沢付近

で、何がやりたいかと云うと...
昔は Google map なんて便利なものがなく地図を眺める趣味もなかったので、古い人間の私は駅の住所から周辺の住所や行政区域をなんとなく把握していました。
東横線と大井町線はよく使っていたので各駅がどの区にあるか把握していたのですが、目黒線(昔は目蒲線)は滅多に使わなかったので駅名すら曖昧な状態。
つまり奥沢はよくしらないけど、その周辺の駅はよくしっているという状態だったわけです。

src = https://github.com/soleil-taruto/StoreH/blob/main/Hatena/a20230108/Hatena20230108/Claes20200001/Claes20200001/Tests/Test0002.cs

奥沢付近

...のように駅があって、それぞれのどの区にあるかというと...

src = https://github.com/soleil-taruto/StoreH/blob/main/Hatena/a20230108/Hatena20230108/Claes20200001/Claes20200001/Tests/Test0003.cs

奥沢付近

...こうしてみると奥沢って目黒区か大田区かなと思っちゃうじゃないですか！！！
というだけの話。
念のため、奥沢は世田谷区です。

src = https://github.com/soleil-taruto/StoreH/blob/main/Hatena/a20230108/Hatena20230108/Claes20200001/Claes20200001/Tests/Test0004.cs

奥沢付近

区境を入れるとこんな感じ。

ここで使ってる src とか
https://github.com/soleil-taruto/StoreH/tree/main/Hatena/a20230108/Hatena20230108/Claes20200001/Claes20200001

Windowsで動くゲームの開発環境を公開してみる (C# + DXライブラリ)

先日書いた記事に便乗します。
　
・・・というのも (C++) + DXライブラリ で書いていたゲームを C# + DXライブラリ に移植するというのを一昨年やって、これを使って何かすごいゲームを作ってやろうとここ数か月意気込んでみたものの、未だ目指すところが定まらず基本的な動作ができたところで進捗が停滞したままなので・・・。だからというのも変ですが まぁ 何かこういうことをやっています的な証跡を残すつもりで開発環境を公開してみます。概ね自分の納得のために！
ニッチな需要しかないだろうなとは思いつつも、DXライブラリでゲームを作りたい人に拾ってもらえたらいいなと思う。

どんな人向けか

  • Windows で動くゲームを作りたい人で昨今流行りの 3D とか興味無い人
    • 現状 Windows しか想定していないが、DXライブラリが各種プラットフォームに対応しているので頑張れば他所でも動くかも。
    • DXライブラリ自体は 3D とかできるっぽいけど、当環境では現状想定していないので 3D は基本無理。やるなら別の方法を検討した方が良い。
  • フレームワークに縛られたくない人、ゲームのコードはすべて自分の制御下に置きたい人
    • 当たり前ですがDXライブラリには縛られます。とは言えDXライブラリはフレームワークと言うよりはその名のとおりライブラリなので、縛りは気にならないと思う。
  • 特にそういうこだわりは無く単にゲームを作りたい・学びたいと考えている人は Unity や Unreal Engine をやるべき！

特徴・注意

ソースコードは C# で記述していて C# 版のDXライブラリとリンクする形で実行する。
その他フレームワークは使用していない。勝手に自動生成されるおまじないコードのようなものは存在せず、出力 .exe の内容はすべて開発者の制御下にあると言って良い。⇐ ここが売り
10 年くらい前に C (C++) で記述したゲームがあって、それを C# へ移植したものをベースにしており、所謂歴史的経緯と、これを書いた者の歪んだ性癖による不条理なプログラム構造を散見する。
VisualStudio 20xx で作っている。

開発環境要件

Windows 10
試してないけど Window 7 ～ 11 でも大丈夫だと思う。// C# のソリューションは Windows 7 の頃から使いまわしているので、7 でも問題無い気がする。
私の環境は Windows 10 Pro

開発環境構築

公開すると言っておきながらなんですが、開発環境が煩雑で一つのアーカイブにまとめるのが難しかったので、ここではソースのみ示します。
　

ソースと実際に動くもの

概要 ソース 実際に動くものへのリンク
ノベルゲーム 試作版 GitHub Download
横スクロール アクション 試作版 1 GitHub Download
横スクロール アクション 試作版 2 GitHub Download
横スクロール アクション 試作版 3 GitHub Download
横スクロール アクション テンプレート 1 GitHub Download
横スクロール アクション テンプレート 2 GitHub Download
横スクロール シューティング テンプレート GitHub Download
ノベルゲーム テンプレート GitHub Download
トップビュー アクション テンプレート GitHub Download

　

で、

ここまで書いておいて「こんなの興味持ってくれる人いるのか？」などと自虐に苛まれる心中はともかく、もし興味があれば当方にご連絡下さい。目的に合わせて環境を開示・提供いたします。(連絡先は GitHub や同梱のマニュアルに記載の ✉ をば)
場合によっては PG としてゲーム制作に参加させていただく対応も可能です。
　

その他リンク

ゲーム試作版テンプレート置き場
http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20221201_Game
_ttp://ornithopter.ccsp.mydns.jp/HPStore/Game

先日こしらえたゲームのダウンロードサイト
http://sword-games.ccsp.mydns.jp

棒消しゲームは先手必勝か後手必勝かどうかについて微考ペガサス

棒消しゲームについて
45mix.net

段数によって先手必勝・後手必勝が分かれるんじゃないかと思って確かめてみたらそうだったという話。
ちなみにこのゲームは引き分けの無い二人零和有限確定完全情報ゲームなので、先手必勝・後手必勝のどちらかになることは間違いない。
こういうゲームの場合、以下のアルゴリズムで良い想定。引き分けも、手番パスも無いのでシンプルに考えられる。

function 勝者の判定 ( $ゲームの局面 ) : 勝者
{
	if ( $ゲームの局面　は勝敗が決している ) // この局面において何方かのプレイヤの勝利条件が達成されているか
	{
		return $ゲームの局面　における勝者 ;
	}

	for ( $指し手 : 手番のプレイヤにできる全ての指し手 )
	{
		if ( 勝者の判定 ( $ゲームの局面 + $指し手 ) == 手番のプレイヤ ) // この局面において手番のプレイヤがこの手で指し進め、勝利するなら ...
		{
			return 手番のプレイヤ ; // ... 手番のプレイヤの勝ちは確定していることになる。
		}
	}

	return 相手側のプレイヤ ; // この局面において手番のプレイヤが何を指しても負けるのなら、相手側のプレイヤの勝ちは確定していることになる。
}

Print "お互い最善手を指せば " + 勝者の判定 ( ゲームの初期状態 ) + " が常に勝利する。" ;

　
実際にやってみた。
コード：

public void Main()
{
	for (int n = 1; ; n++)
	{
		Console.WriteLine(n + " 段の場合 " + (GetWinner(Enumerable.Range(1, n).ToArray()) == Player_e.Me ? "先手必勝" : "後手必勝") + " です。");
	}
}

private enum Player_e
{
	Me,
	Another,
}

private Player_e GetWinner(IList<int> rows) // rows: 各行の(連続する)棒の本数 , ret: 自分(Player_e.Me)を手番とした場合のこの局面における勝者
{
	if (rows.Count == 0) // 直前に相手が消した棒が最後なら、相手の負け。
	{
		return Player_e.Me; // つまり勝者は自分
	}

	for (int i = 0; i < rows.Count; i++) // 全ての行について
	{
		int row = rows[i];

		for (int s = 0; s < row; s++) // 消し始めの位置
		{
			for (int c = 1; s + c <= row; c++) // 消す本数
			{
				int l = s; // 分断された行の左側
				int r = row - (s + c); // 分断された行の右側

				List<int> next = new List<int>(); // 次の局面を作る。

				next.AddRange(rows.Take(i)); // 消した行の前側
				next.AddRange(rows.Skip(i + 1)); // 消した行の後側

				// 分断された部分を独立した行と見なして追加する。
				if (l != 0) next.Add(l);
				if (r != 0) next.Add(r);

				if (GetWinner(next) == Player_e.Another) // 次の局面以降において自分の勝ちが確定するなら ...
				{
					return Player_e.Me; // ... 勝者は自分
				}
			}
		}
	}

	return Player_e.Another; // 勝ち目が無ければ、勝者は相手側
}

で、
これを実行したらやたら重かったので、勝者をキャッシュして同じ局面については再探索しないように修正したのが以下。
コード：

public void Main()
{
	for (int n = 1; ; n++)
	{
		Console.WriteLine(n + " 段の場合 " + (GetWinner(Enumerable.Range(1, n).ToArray()) == Player_e.Me ? "先手必勝" : "後手必勝") + " です。");
	}
}

private enum Player_e
{
	Me,
	Another,
}

private Player_e GetWinner(IList<int> rows) // rows: 各行の(連続する)棒の本数_昇順であること , ret: 自分(Player_e.Me)を手番とした場合のこの局面における勝者
{
	if (rows.Count == 0) // 直前に相手が消した棒が最後なら、相手の負け。
	{
		return Player_e.Me; // つまり勝者は自分
	}

	string strRows = RowsToString(rows);

	if (WinnerCache.ContainsKey(strRows)) // 既知の局面なら、既知の勝者を返す。
	{
		return WinnerCache[strRows];
	}

	for (int i = 0; i < rows.Count; i++) // 全ての行について
	{
		int row = rows[i];

		for (int s = 0; s < row; s++) // 消し始めの位置
		{
			for (int c = 1; s + c <= row; c++) // 消す本数
			{
				int l = s; // 分断された行の左側
				int r = row - (s + c); // 分断された行の右側

				List<int> next = new List<int>(); // 次の局面を作る。

				next.AddRange(rows.Take(i)); // 消した行の前側
				next.AddRange(rows.Skip(i + 1)); // 消した行の後側

				// 分断された部分を独立した行と見なして追加する。
				if (l != 0) next.Add(l);
				if (r != 0) next.Add(r);

				next.Sort((a, b) => a - b); // 昇順にソートする。

				if (GetWinner(next) == Player_e.Another) // 次の局面以降において自分の勝ちが確定するなら ...
				{
					WinnerCache.Add(strRows, Player_e.Me); // この局面における勝者を記憶

					return Player_e.Me; // ... 勝者は自分
				}
			}
		}
	}

	WinnerCache.Add(strRows, Player_e.Another); // この局面における勝者を記憶

	return Player_e.Another; // 勝ち目が無ければ、勝者は相手側
}

private Dictionary<string, Player_e> WinnerCache = new Dictionary<string, Player_e>();

private string RowsToString(IList<int> rows)
{
	return string.Join("_", rows);
}

出力：

1 段の場合 後手必勝 です。
2 段の場合 先手必勝 です。
3 段の場合 後手必勝 です。
4 段の場合 先手必勝 です。
5 段の場合 先手必勝 です。
6 段の場合 先手必勝 です。
7 段の場合 後手必勝 です。
8 段の場合 先手必勝 です。
9 段の場合 先手必勝 です。
10 段の場合 先手必勝 です。
^C

　
まだ重い気がするけど、10 段以下で先手必勝・後手必勝が分かれるのが見れたので満足。
微考終了。

素数の列挙 (JavaScript)

前にもやったけど
エラトステネスの篩をビットリストを使わないようにやってみたら、そこそこ気持ち悪い実装になったので、ここに残しておく。
下記コード中の Primes(max) 関数が max 以下の素数を小さい方から列挙する。
Primes はジェネレータなので Primes(Infinity); としてもよい。(というか max 自体取っ払ってもよかった)
数の大きさ的には Gaps の n * (n - 1) - 1 あたりがボトルネックなので、メモリ消費と処理時間を考えなければ Math.sqrt(Number.MAX_SAFE_INTEGER) あたりまで列挙できるはず。
　
Paiza.io ⇒ _ttps://paiza.io/projects/IG6vs6022qrOnxqX9u1mQw
Paiza.io ⇒ https://paiza.io/projects/efEgQU8Kdcy8Jp6roaOj4Q

コード：

function* Endless(v) {
    for (; ; ) {
        yield v;
    }
}

function* Repeat(v, n) {
    for (var i = 0; i < n; i++) {
        yield v;
    }
}

function* Gaps(n) {
    yield n * (n - 1) - 1;
    yield* Endless(n - 1);
}

function* Sieve(gaps) {
    for (; ; ) {
        yield* Repeat(1, gaps());
        yield 0;
    }
}

function Supplier(e) {
    return () => e.next().value;
}

function Both(a, b) {
    return () => a() & b();
}

function* Primes(max) {
    var s = () => 1;
    
    for (var n = 2; n <= max; n++) {
        if (s()) {
            s = Both(s, Supplier(Sieve(Supplier(Gaps(n)))));
            yield n;
        }
    }
}

for (var n of Primes(100)) {
    console.log(n);
}

出力：

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

ブラウザで動くゲームの開発環境を公開してみる

先日作ったブラウザで動くゲームをサイトに仕立ててみた。
http://shield-games.ccsp.mydns.jp/entrance
　
・・・仕立ててみたものの、ゲームを充実させて人が来てくれるようになるまで大分掛かりそうなこととブラウザ版の Unity の趨勢に鑑みると、このままでは幾ばくもなく諸々の下に埋もれてしまいそうなので、今のうちに開発環境を公開するというアクションを起こしてみることにした。
ニッチな需要しかないだろうなとは思いつつも、ブラウザで動くゲームを作りたい人に拾ってもらえたらいいなと思う。

どんな人向けか

  • ブラウザで動くゲームを作りたい人で昨今流行りの3Dとか興味無い人
  • フレームワークに縛られたくない人、ゲームのコードはすべて自分の制御下に置きたい人
  • 特にそういうこだわりは無く単にゲームを作りたい・学びたいと考えている人は Unity や Unreal Engine をやるべき！

特徴・注意

ソースコードは基本的にプレーン JavaScript で記述されている。本開発環境固有の記述を含んでいるが、大したものではないのでプレーン JavaScript が扱えれば問題無い。
ソースコードとリソースは変換ツール (JSJoin.exe) を使って html ファイルに変換し、実行する。コンパイラ言語のような使い勝手である。(JSJoinは後述する開発環境に同梱している)
フレームワークは使用していない。勝手に自動生成されるおまじないコードのようなものは存在せず、出力 html の内容はすべて開発者の制御下にあると言って良い。⇐ ここが売り
10 年くらい前に C (C++) で記述したゲームがあって、それを C# へ移植したものを JavaScript に横展開したものなので、所謂歴史的経緯による不条理なプログラム構造を散見する。
また私自身が JavaScript の経験が少なく C を愛用していた期間が長いため、C っぽい記述になっている。
具体的には、プログラム全体はグローバルスコープ・ファイルスコープの関数と変数の集合によって構成され、連想配列は C の struct のように扱っている。
もしかすると JavaScript は知らないけど C ならよく使っているという人に取っ付きやすいかもしれない。
IDE は使っていない。エクスプローラと秀丸のみ。もちろんエディタは何を使っても良いけど tags を使うので秀丸だとより良い。

開発環境要件

Windows 10
試してないけど Window 7 ～ 11 でも大丈夫だと思う。
私の環境は Windows 10 Pro

開発環境構築

とりあえず開発環境の構築手順のみ示す。
プログラムの説明はいずれ・・・
　
手順といっても以下のファイルをダウンロードして、ローカルディスク上の任意の場所に展開するだけである。
http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20220924_Develop
⇒ GameJS.zip をダウンロードする。
　
GameJS.zip の中身 (アーカイブ直下のフォルダ構成) は以下のとおり

フォルダ 説明 実際に動くものへのリンク
bin 変換ツール置き場 　
Cirno ゲームその1　横スクロール・2Dアクションゲーム http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20220924_GameJS/Cirno
Doremy ゲームその2　ロックマン風の2Dアクションゲーム http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20220924_GameJS/Doremy
Marisa ゲームその3　トップビューの2Dアクションゲーム http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20220924_GameJS/Marisa
Shooting ゲームその4　縦スクロール・2Dシューティングゲーム http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20220924_GameJS/Shooting

どのようなゲームかは実際に動くものへのリンクでご確認下さい。
開発環境のビルドを行えば、実際に動くものへのリンクにあるものと同じもの(※)を生成できます。
　
※ フリー素材の画像・音楽はアーカイブに同梱すると再配布となって利用規約に抵触するため、ダミーの画像・無音の音声ファイルに置き換えています。各ゲームのリソースフォルダ ( res フォルダ) の配下は取得先別にフォルダ分けされていて、その中の _source.txt というファイルに取得先が書いてあります。お手数ですが、情報を元にデータの再取得をお願いします。ちなみに再取得しなくても (ダミー画像＆無音にはなってしまいますが) ビルドはできます。
　

ビルド手順

デバッグ用

各ゲームフォルダの下にある Debug.bat を実行する。(実行時のカレントディレクトリは Debug.bat と同じ場所であること)
ビルドに成功すると out フォルダ直下に index.html が生成される。
index.html を開くことでゲームを遊ぶことができる。
(リソースフォルダ内のファイルに直リンクしていることに注意すること)

リリース用

各ゲームフォルダの下にある Release.bat を実行する。(実行時のカレントディレクトリは Release.bat と同じ場所であること)
ビルドに成功すると out フォルダ直下に index.html と _res フォルダが生成される。
index.html を開くことでゲームを遊ぶことができる。
(どこかへ移動したりサーバーにアップロードするときは _res フォルダも必要になるので注意すること)

捕捉

GitHubに置いたソースなど
各ゲームについては上記 GameJS.zip に収録しているものと同じなので、何なら GitHub からダウンロードしても可。却って面倒くさいかもだけど。

ツール・ゲーム GitHub
JSJoin https://github.com/soleil-taruto/Store/tree/main/Hatena/a20220923/JSJoin
Cirno https://github.com/soleil-taruto/Store/tree/main/Hatena/a20220923/GameJS/Cirno
Doremy https://github.com/soleil-taruto/Store/tree/main/Hatena/a20220923/GameJS/Doremy
Marisa https://github.com/soleil-taruto/Store/tree/main/Hatena/a20220923/GameJS/Marisa
Shooting https://github.com/soleil-taruto/Store/tree/main/Hatena/a20220923/GameJS/Shooting

変換ツール (JSJoin) のみ落としたい場合：
http://ornithopter.ccsp.mydns.jp/HPStore/Hatena/20220924_JSJoin
⇒ JSJoin.zip をダウンロードする。