今日の"どう書く"問題のアルゴリズム例

Nagoya.php #17 補足資料
https://nagoyaphp.connpass.com/event/139314/

Transcript

1. ࠓ೔ͷ”Ͳ͏ॻ͘”໰୊ͷ ΞϧΰϦζϜྫ 2019/08/28 #nagoyaphp @ttskch
2. ๻ʹ͍ͭͯ
3. ͖ͨͭͪʢ໊͋ͩʣ • (ג)ΧϧςοτίϛϡχέʔγϣϯζCTO • WebΤϯδχΞྺ7೥ɺPHPྺ7೥ • #nagoyaphpʊ • #symfony_meetup
4. ͖ͨͭͪʢ໊͋ͩʣ • ͓ख఻͍ͨ͠ຊʢ2015/12ʣ • Schooߨࢣʢ2018/04ʣ ʮGitHubΛ࢖ͬͨσϓϩΠࣗಈԽ࣮ફʯ ʮجຊ͔Β͔ͬ͠ΓֶͿ Symfony2ೖ໳ʯ
5. ͨ ͭ ͖ ͪ twitter.com/ttskch ͋͞ɺ͋ͳͨ΋ࠓ͙͢ϑΥϩʔ͠Α͏!!! ׬શແྉ ·͞ʹ໊ݴ੡଄ػ ਓੜͰେ੾ͳ͜ͱ͸ɺ͢΂ͯ ͖͔ͨͭͪΒڭΘͬͨ ͖ͨͭͪΛϑΥϩʔͨ͠Β
 ࠊ௧͕࣏Γ·ͨ͠ 100% φϯτʂ ϑΥϩϫʔ͔Βͷࢧ࣋཰ 100% ͍ͯ͠Δ ͍ͯ͠ͳ͍ ϑΥϩϫʔ͞Μ100ਓʹฉ͖·ͨ͠ ͖ͨͭͪΛϑΥϩʔ͍ͯ͠Δʁ
6. ձࣾʹ͍ͭͯ
7. (ג)Χϧςοτίϛϡχέʔγϣϯζ https://quartet-communications.com
8. (ג)Χϧςοτίϛϡχέʔγϣϯζ https://www.google.co.jp/search?q=Χʔςϯ
9. (ג)Χϧςοτίϛϡχέʔγϣϯζ https://lisket.jp
10. We are hiring!ʢϚδͰʣ • PHPer/JSerઈࢍେืूதʂʢϦϞʔτ΍όΠτ΋Մʣ • Symfony+AngularͰɺWeb޿ࠂۀքΛ
 ϗϫΠτʹ͢Δ࢓૊ΈΛ࡞ͬͯ·͢ • ܦӦϏδϣϯ͸ʮੈքҰޮ཰తͳ୅ཧళʯ
11. We are hiring!ʢϚδͰʣ • ࣗࣾαʔϏεʮLisketʯͰࣗࣾͷۀ຿΋ޮ཰Խ • શࣾһͷฏۉ࢒ۀ͕࣌ؒ5h/݄͙Β͍Ͱ͢ ಛผ৆ड৆
12. We are hiring!ʢϚδͰʣ ΤϯδχΞͷಇ͖΍͢͞௒େࣄʹͯ͠·͢✨
13. We are hiring!ʢϚδͰʣ ·ͣ͸͓࿩͚ͩͰ΋ʂؾܰʹ੠͔͚͍ͯͩ͘͞
14. /30 We are hiring!ʢϚδͰʣ ࠾༻αΠτ΋͋Γ·͢ʂͥͻ೷͍ͯΈ͍ͯͩ͘͞ 14 https://quartetcom.co.jp/recruit/engineer/
15. ࠓ೔ͷ”Ͳ͏ॻ͘”໰୊ͷ ΞϧΰϦζϜྫ 2019/08/28 #nagoyaphp @ttskch
16. http://nabetani.sakura.ne.jp/hena/orde16nontri/
17. ී௨ʹ΍Δͱ
18. public function run(string $input) : string { $dec = intval($input); while (true) { $bin = decbin(strval(++$dec)); if (strpos($bin, '000') === false && strpos($bin, '111') === false) { return strval($dec); } } } 1૿΍͠ͳ͕Βɺஞ࣍ʮඇࡾ࿈਺͔ʁʯΛνΣοΫ͢Δ
19. public function run(string $input) : string { $dec = intval($input); while (true) { $bin = decbin(strval(++$dec)); if (strpos($bin, '000') === false && strpos($bin, '111') === false) { return strval($dec); } } } 1૿΍͠ͳ͕Βɺஞ࣍ʮඇࡾ࿈਺͔ʁʯΛνΣοΫ͢Δ ೖྗ஋ͱظ଴஋ͷࠩʹൺྫͯ͠ ܭࢉྔ͕૿͑Δ
20. public function run(string $input) : string { $dec = intval($input); while (true) { $bin = decbin(strval(++$dec)); if (strpos($bin, '000') === false && strpos($bin, '111') === false) { return strval($dec); } } } 1૿΍͠ͳ͕Βɺஞ࣍ʮඇࡾ࿈਺͔ʁʯΛνΣοΫ͢Δ ೖྗ஋ͱظ଴஋ͷࠩʹൺྫͯ͠ ܭࢉྔ͕૿͑Δ 100000000000000 (2) ͱ͔Λೖྗ͞ΕΔͱϠόΠ
21. ޻෉ͯ͠ΈΔ
22. ྫ୊ᶃ 22
23. ྫ୊ᶃ 23 100010110001
24. 24 100010110001 ࠷ॳͷ 000 Λݟ͚ͭΔ ྫ୊ᶃ
25. 25 100110110001 ͦΕΛ 001 ʹஔ͖׵͑Δ ྫ୊ᶃ
26. 26 100110110001 ଓ͖Λ͢΂ͯ 001001... Ͱஔ͖׵͑Δ ྫ୊ᶃ
27. 27 100100100100 ଓ͖Λ͢΂ͯ 001001... Ͱஔ͖׵͑Δ ྫ୊ᶃ
28. 28 100100100100 ׬੒ ྫ୊ᶃ
29. ྫ୊ᶄ 29
30. ྫ୊ᶄ 30 101110101101
31. 31 101110101101 ࠷ॳͷ 0111 Λݟ͚ͭΔ ྫ୊ᶄ
32. 32 110010101101 ͦΕΛ 1001 ʹஔ͖׵͑Δ ྫ୊ᶄ
33. 33 110010101101 ଓ͖Λ͢΂ͯ 001001... Ͱஔ͖׵͑Δ ྫ୊ᶄ
34. 34 110010010010 ଓ͖Λ͢΂ͯ 001001... Ͱஔ͖׵͑Δ ྫ୊ᶄ
35. 35 110010010010 ׬੒ ྫ୊ᶄ
36. ·ͱΊΔͱ 36
37. 37 000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ000Λ001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ
38. 38 000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ000Λ001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ
39. 39 000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ000Λ001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ ઌ಄͕111ͩͬͨΒʁ
40. 40 000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ000Λ001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ
41. 41 000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ000Λ001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ
42. 42 000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ000Λ001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ ͞Βʹͻͱ޻෉…
43. 43 1000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ1000Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ
44. 44 1000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ1000Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ
45. 45 1000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ1000Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ࠷ॳͷ0111Λ1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ
46. 46 1000͕ઌʹ ͋Δ৔߹ ࠷ॳͷ1000·ͨ͸0111Λ 1001ʹஔ׵ͯ͠ ࢒ΓΛ001ͷ॥؀ͰຒΊΔ 0111͕ઌʹ ͋Δ৔߹ ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ
47. ྫ୊ᶅ 47
48. ྫ୊ᶅ 48 110111010110
49. ྫ୊ᶅ 49 01101110101100 ઌ಄ʹ 0 Λ෇༩͢Δ
50. 50 01101110101100 ࠷ॳͷ 0111 Λݟ͚ͭΔ ྫ୊ᶅ
51. 51 01110010101100 ͦΕΛ 1001 ʹஔ͖׵͑Δ ྫ୊ᶅ
52. 52 01110010101100 ଓ͖Λ͢΂ͯ 001001... Ͱஔ͖׵͑Δ ྫ୊ᶅ
53. 53 01110010010010 ଓ͖Λ͢΂ͯ 001001... Ͱஔ͖׵͑Δ ྫ୊ᶅ
54. 54 111001001001 ׬੒ʁ ྫ୊ᶅ
55. 55 111001001001 ൱ʂ ྫ୊ᶅ
56. མͱ݀͠ 56 • 0111Λ1001ʹஔ׵ͨ͜͠ͱͰɺ
 111͕৽ͨʹ࡞ΒΕͯ͠·͏৔߹͕͋Δ • ಉ͡ૢ࡞Λ܁Γฦ͢ඞཁ͕͋Δʂ
57. ݁࿦ 57
58. 58 • ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ • ࠷ॳͷ1000·ͨ͸0111Λ1001ʹஔ׵ͯ͠ • ࢒ΓΛ001ͷ॥؀ͰຒΊΔ • ઌ಄ͷ0ΛऔΓআ͘ • …ͱ͍͏ૢ࡞Λඇࡾ࿈਺ʹͳΔ·Ͱ܁Γฦ͢
59. 59 • ͋Β͔͡Ίઌ಄ʹ0Λ෇༩্͓͍ͯͨ͠Ͱ • ࠷ॳͷ1000·ͨ͸0111Λ1001ʹஔ׵ͯ͠ • ࢒ΓΛ001ͷ॥؀ͰຒΊΔ • ઌ಄ͷ0ΛऔΓআ͘ • …ͱ͍͏ૢ࡞Λඇࡾ࿈਺ʹͳΔ·Ͱ܁Γฦ͢
60. ࣮૷ྫ
61. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } }
62. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } Ұ࿈ͷॲཧΛ܁Γฦ͢
63. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } 2ਐ਺ʹม׵ͯ͠ઌ಄ʹ0Λ෇༩
64. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } ࠷ॳͷ1000·ͨ͸0111Λ୳͢
65. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } ݟ͔ͭΒͳ͚Ε͹ඇࡾ࿈਺ͷ׬੒
66. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } ઌ಄ͷ0ΛऔΓআ͖ͭͭ (1000|0111)ΑΓલͷ෦෼Λୀආ
67. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } (1000|0111)ΑΓޙͷ෦෼Λ001...Ͱஔ׵
68. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } } ʮલʴ1001ʴޙʯͱ࿈݁ͯ͠10ਐ਺ʹ
69. public function run(string $input) : string { $dec = intval($input) + 1; while (true) { $bin = '0' . decbin($dec); preg_match('/(.*?)(1000|0111)(.*)/', $bin, $m); if (empty($m)) { return strval($dec); } $head = ltrim($m[1], '0'); $tailLength = strlen($m[3]); $tail = substr( str_repeat('001', intval(floor($tailLength / 3)) + 1), 0, $tailLength); $dec = strval(bindec($head . '1001' . $tail)); } }
70. https://github.com/ ttskch/nagoyaphp17
71. @ttskch ʘThanks!ʗ