taxicat1.github.io
Reversing an integer hash function This is an integer hash function written by Thomas Wang: uint32_t hash6432shift(uint64_t key) { key = (~key) + (key << 18); key ^= key >> 31; key *= 21; key ^= key >> 11; key += key << 6; key ^= key >> 22; return 0xFFFFFFFF & key; } It hashes down a 64-bit input to a 32-bit output. It has good mixing: basic statistical analysis can show that it has reasonably goo
「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム― – Ono Laboratory
はじめに 最近，「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました（東北大学の江藤宏先生，九州大学の木谷裕紀先生との共同研究．国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表．2021年12月30日現在，pdfはここから取れます）． これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき，かつそれを一般化した場合，どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析したものです．今回「最適化技術の応用・実践」に関する記事を集めよう，ということになりましたので，ちょうどよい題材ということで，この研究をより一般向けに解説してみようと思います．一般向けですので証明自体には踏み込まず，既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします．ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象とし
6x6リバーシの神 - まめめも
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。 絶対に勝てない6x6リバーシを作りました！ ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp— Yusuke Endoh (@mametter) December 30, 2021 これは何？ 6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。 技術的な話 このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。 AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。 github.com 作った順に説明します。 盤面の表現
「アルゴ式」をHaskellで学ぶための準備
この記事は、CAMPHOR- Advent Calendar 2021 の7日目の記事です。 「アルゴ式」というプログラミングを学んで実践できる非常に良質なWebサービスがあります。 アルゴリズムについて解説された教科書だけでなく、実際にプログラミングを書いて提出してオンラインでジャッジしてくれるシステムを備えた練習問題も用意されているのが特徴です。さらにこのオンラインジャッジシステムは多くのプログラミング言語に対応しており、その中にはHaskellも含まれています。 今回はこのアルゴ式を読むにあたって練習問題をHaskellで解くために必要になりそうな知識についてまとめました。アルゴ式は現在ベータ版なので将来的な変更で変わってしまうものもあるかもしれませんが、2021年12月現在の練習問題を全てHaskellで解いた上で必要になったものをまとめているので参考にしていただけると幸いです。
AHC006初心者向け解説 ～貪欲だけで順位表2ページ目を目指す～ - TERRYのブログ
ヒューリスティックコンテスト、楽しんでますか？私は楽しんでいます。最近企業AHCなんかも続々と出てきて、これからどんどん盛り上がってくれるんじゃないかと期待しています。 とはいえ、ヒューリスティックコンテスト特有の取っつきづらさがあるのも確かです。「どこから手を付けていいか分からない……」「AHC後のTLに焼きなましとか2-optとか流れてきたけど何が何だか……」と思われた方も多くいらっしゃるのではないでしょうか？ AHC006は巡回セールスマン問題を発展させた問題なので、確かに2-optを使った焼きなましができると有利ではあります。しかし、専門知識がないと戦えないかというと全くそんなことはありません。 この記事では、AtCoder Heuristic Contest 006 (AHC006)を題材として、 焼きなまし → 使いません ビームサーチ → 使いません 2-opt → もちろん
PhobosLab
Introducing QOI — the Quite OK Image Format. It losslessly compresses RGB and RGBA images to a similar size of PNG, while offering a 20x-50x speedup in compression and 3x-4x speedup in decompression. All single-threaded, no SIMD. It's also stupidly simple. tl;dr: 300 lines of C, single header, source on github, benchmark results here. I want to preface this article by saying that I have no idea wh
Peritext: A CRDT for Rich-Text Collaboration
Two editors are asynchronously collaborating on a rich-text document. Each editor makes local changes, and when they periodically sync, the Peritext CRDT ensures that they converge to seeing the same formatted document. This example is live running code. A revised PDF version of this article has been accepted to CSCW 2022 and published in the PACM HCI journal. Please cite it as: Geoffrey Litt, Sar
Implementing Hash Tables in C
NOTE(s): The article is in “draft” status. The content was originally written in 2017. The intended audience for this article is undergrad students or seasoned developers who want to refresh their knowledge on the subject. The reader should already be familiar with C (pointers, pointer functions, macros, memory management) and basic data structures knowledge (e.g., arrays, linked lists, and binary
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
How We Made Bracket Pair Colorization 10,000x Faster In Visual Studio Code
Version 1.93 is now available! Read about the new features and fixes from August. Bracket pair colorization 10,000x faster September 29, 2021 by Henning Dieterichs, @hediet_dev When dealing with deeply nested brackets in Visual Studio Code, it can be hard to figure out which brackets match and which do not. To make this easier, in 2016, a user named CoenraadS developed the awesome Bracket Pair Col
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - viega/hatrack: Fast, multi-reader, multi-writer, lockless data structures for parallel programming
30 Weird Chess Algorithms: Elo World
A tale of Java Hash Tables
1000x Faster Spelling Correction algorithm
Duff’s device in 2021 – Belay the C++
https://offbeat.cc/blog/time-for-programming-puzzles.html
GitHub - Const-me/LookupTables
Is this the simplest (and most surprising) sorting algorithm ever? | Lobsters
ICFP'21 Tutorials - Programming with Effect Handlers and FBIP in Koka
Proving 50-Year-Old Sorting Networks Optimal: Part 2