modalsoul’s blog

これは“失敗”と呼べるかもしれないが、ぼくは“学習体験”と呼びたい

LeetCode 3. Longest Substring Without Repeating Characters

LeetCode problem No.3.

No.2 is here. modalsoul.hatenablog.com

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Given a string, find the length of the longest substring without repeating characters.

Example

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Code

object Solution {
    def lengthOfLongestSubstring(s: String): Int = {
        s.foldLeft((Seq.empty[Char], if(s.length > 0) 1 else 0)){ (z, c) =>
          if(z._1.contains(c)) ((z._1 :+ c).dropWhile(n => n != c).tail, z._2)
          else (z._1 :+ c, if(z._1.length + 1 > z._2) z._1.size + 1 else z._2)
        }._2
    }
}

Methods

  • Read a character and make substring.
  • If current substring has the same character, drop characters before the same character to take sub-substring that doesn't have the same character.
  • if current substring does not have the same character, add a character at the end to current substring.
  • Count longest substring length.
  • z:(Seq[Char], Int)
    • z._1 is current substring.
    • z._2 is current longest substring length.
  • c:Char
    • c is the current character.

Results

All testcase passed, but it is not fast.

Runtime: 464 ms, faster than 47.37% of Scala online submissions for Longest Substring Without Repeating Characters. Memory Usage: 59.2 MB, less than 5.55% of Scala online submissions for Longest Substring Without Repeating Characters.

LeetCode 2. Add Two Numbers

LeetCode 2問目

1問目はこれ modalsoul.hatenablog.com

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

負でない整数2つを表すリンクリストが2つ与えられる

このリストは、それぞれのノードに整数の各桁が逆順に格納されている

この整数の和を求め、リンクリストとして返却する

Examples

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

コードその1

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        def calc(l:ListNode):Int = {
            var result = 0L
            var hasNext = true
            var c = l
            var digit = 1
            while(hasNext) {
                result = c.x * digit + result
                if(c.next == null) hasNext = false
                c = c.next
                digit = digit * 10
            }
            result
        }
        var sum = calc(l1) + calc(l2)
        var head = new ListNode(_x = sum%10)
        var prev:ListNode = head
        sum = sum/10
        while(sum > 0) {
            val next = new ListNode(_x = sum%10)
            prev.next = next
            prev = next
            sum = sum/10
        }
        head
    }
}

考えたこと

  • リンクリストを数値に戻し、足し算する
  • 足し算の結果をリンクリストへ変換する

これだとExampleのようなケースでは動くけど、リンクリストの長さが増えると動かない

コードその2

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        def run(a:ListNode, b:ListNode, acc:ListNode = null, prev:ListNode = null, carried:Boolean = false): ListNode = {
          if(a == null && b == null) {
            if (carried) prev.next = new ListNode(_x = 1)
            acc
          }
          else {
            val x = (if(a != null) a.x else 0) + (if(b != null) b.x else 0) + (if(carried) 1 else 0)
            val node = new ListNode(_x = x%10)
            if(acc == null) {
              run(a.next, b.next, acc = node, prev = node, x > 9)
            }
            else {
              prev.next = node
              run(if(a == null) null else a.next, if(b == null) null else b.next, acc = acc, prev = node, x > 9)
            }
          }
        }
        run(l1, l2)
    }
}

考えたこと

  • リンクリストを辿る時点でその桁の足し算をしてしまう
  • 桁の繰り上がり有る無しを持ち回す

こっちはすべてのテストケースをパスした

Runtime: 380 ms, faster than 99.59% of Scala online submissions for Add Two Numbers. Memory Usage: 58.2 MB, less than 78.57% of Scala online submissions for Add Two Numbers.

LeetCode 1. Two Sum

某入社エントリーに影響を受けてLeetCodeをはじめてみた

leetcode.com

最近プライベートで書くコードがスマートホーム系のちょっとしたPythonスクリプトばかりで飽きてきたので、Scalaの手直しも兼ねてやってみる

1. Two Sum

https://leetcode.com/problems/two-sum/

Intの配列が与えられるので、和が指定される値と等しくなる2つの数値のインデックスを返す

入力に対して必ず解が存在し、同じ値を2度使うことはない

Example:

Given nums = [2, 7, 11, 15], target = 9

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

考えたこと

  • リストなのでheadtailに分けて考えよう
  • headの値とtailのいずれかの値の和が、targetと等しくなった場合、headのインデックスとtailの値のインデックスを返せばOK
  • tailのいずれの値でもtargetと等しくならない場合、tailをさらにheadtailに分けて考える(以下繰り返し

コードその1

object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        def index(n1:Int, arr:Array[Int]):Option[Int] = {
          val res = arr.indexWhere(_ + n1 == target) + 1
          if(res != 0) Some(res) else None
        }

        def run(nums:Array[Int], offset:Int = 0):Array[Int] = {
          index(nums.head, nums.tail) match {
            case Some(n2) => Array(offset, n2 + offset)
            case _ => run(nums.tail, offset + 1)
          }
        }
        run(nums)
    }
}

解説

def index(n1:Int, arr:Array[Int]):Option[Int]

任意のn1との和がtargetと等しくなる値のインデックスのオプションを返す

Seq.indexWhereの戻り型をIntからOption[Int]へ変換するためのもの

Seq.indexWhereOption:Option[Int]のようなメソッドがあれば良かったんだが。。

def run(nums:Array[Int], offset:Int = 0):Array[Int]

numsのheadに対して条件を満たす値がtailに存在するか否か

indexの結果をパターンマッチして、Someの場合に解発見、Noneの場合再帰する

tailを遡るたびにindexが進むので、その回数をoffsetで持ち回る

考察

一応できたけれど、O(n2)

改善の余地あり

コードその2

object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        val map = nums.zipWithIndex.toMap
        nums.zipWithIndex.foldLeft(Array.empty[Int]){(z, n) =>
          if(!z.isEmpty) z
          else {
            val t = target - n._1
            map.get(t).fold(z){ x => if(x != n._2) Array(n._2, x) else z}
          }
        }
    }
}

解説

  • n番目の値のインデックスとn番目の値をtargetから引いた値のインデックスが解になる
  • 値とインデックスのマップを生成

これでO(n)

コードその3

object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        nums.zipWithIndex.foldRight((Map.empty[Int, Int], Array.empty[Int])) { (n, z) =>
          if(!z._2.isEmpty) z
          else {
            val (map, acc) = z
            val (num, index) = n
            (map + n, map.get(target - num).fold(acc){ x => if(x != index) Array(index, x) else acc})
          }
        }._2
    }
}

解説

  • 基本的な考え方はコードその2と同じ
  • 値とインデックスのマップ生成時に、和がtargetになる値の有無をチェックする

Luhnアルゴリズムによる誤り検出

Luhnアルゴリズムについてちょっと話題に上がったので書いてみる

Luhnアルゴリズム 1

クレジットカード番号やIMEI番号の検証に使われているアルゴリズム

  • 任意の1桁の間違いや隣接する桁の数字の順序間違いを検出できる
  • 09 から 90 (または逆)という間違いは検出できない
  • 同じ数字が2つ連続する場合の間違いも10種類のうち4種類までは検出できる
    • 22 ⇔ 55、33 ⇔ 66、44 ⇔ 77 は検出できない

記入ミスやタイプミスを検出するもので、クレジットマスターを防ぐことはできない (ここテストにでます

IMEI番号は電話のキーパッド*#06#と入力すると表示される

検証手順

  • 右端のチェックディジットを1番目として、偶数番目の桁を2倍にする。
  • 2倍にしていない桁も含め、各数字の総和を求める(2倍にした桁が2桁になった場合は、それぞれを別々の数字として加える)。
  • この総和の下1桁が0なら(つまり、10で割り切れる場合)、この番号はLuhnアルゴリズムでは正しく、そうでない場合は正しくない。

実装

これをScalaで実装してみた

Raspberry Pi Zeroで車載機をDIYしたときのアレコレとその先

これはRaspberry Pi Advent Calendar 2018の2日目の記事です。

adventar.org


modalsoul.hatenablog.jp

↑の記事のなかで、Raspberry Pi Zero WHを使った車載機を作ったときのアレコレを書いてみます

使ったもの

9軸センサー

modalsoul.hatenablog.com

車両の状態変化を観測するために9軸センサーを使用

小学生のとき以来?のはんだ付け

FaBo9Axis_MPU9250モジュールをPython3系で使ったときに、MPU9250.pyprint "~"Syntax Errorになってハマったのはモニョッたぜ。。

GPS

modalsoul.hatenablog.com

車両の位置情報を取得するのにみちびき対応のGPS受信機キットを使用

配線をミスって、RxD <-> RxD、TxD <-> TxDと繋いでいることに気づかず、設定を何度もチェックするという。。

俺はなぜあんな無駄な時間を・・・

みちびき4機対応のファームアップデートしないとなー

Bluetooth

modalsoul.hatenablog.com

セキュリティのON/OFFを判定するのに、Bluetoothバイスのスキャンを使った

ほんとうはBLEのBeaconタグを使うつもりだったけど、間に合わず

BLE Beaconを受信するところがなんかうまくいかなかったので、もうちょっと調べたい

スピーカー

modalsoul.hatenablog.com

システム音声を再生するのに使った

ほんとうに音量が控えめ、悟りを開きそうになるくらい耳を澄まさないと聞こえない。。

今回のシステム音声は予め用意した音声ファイルを使ったけど、Raspberry Pi音声合成するのも試してみたい

物理ボタン

modalsoul.hatenablog.com

Raspberry Piをいじる上で、物理ブート/シャットダウンボタンはほんとうに役に立った

スイッチはトグルタイプに変えたさある

使いたいもの

電子ペーパー

やっぱりスピーカーとLEDランプ以外の出力が欲しい

けれど、消費電力の都合上ディスプレイは厳しそうなんで、電子ペーパー使ってみたいですね

フリップドットディスプレイ

iizukak.hatenablog.jp

フリップドットディスプレイつけたいんですが、気軽に手に入るのないですかね?

多謝

Raspberry Pi Zeroについて

GPIOのピン、どうやっても並びを覚えられなくて、どっちから数えて何番目だっけ?ってとき、このページのハードウェア図は何度も参照しました

この場を借りて感謝

最後に

今年の秋頃からぽつぽつとRaspberry Piをいじりだして、まだわからないことのほうが多いけど、こんな感じで楽しくやっていきたいですねー

Raspberry Pi Zero WHで、 BLE Beaconを送信する&Bluetoothデバイス名を変更する

Raspberry Pi Zero WHは、Bluetooth4.0/BLE(Bluetooth Low Energy)が使えるので、Beaconの送信をしてみた

Bluez

LinuxオフィシャルなBluetoothスタックのBluezを使います

Bluez-ibeaconのインストール

手っ取り早くBluez-iBeacon github.com

cd /usr/local/src
sudo git clone https://github.com/carsonmcdonald/bluez-ibeacon.git
cd bluez-ibeacon/bluez-beacon/
sudo make

Usage

cd bluez-ibeacon/bluez-beacon/
./ibeacon
Usage: ./ibeacon <advertisement time in ms> <UUID> <major number> <minor number> <RSSI calibration amount>

Beaconの送信

sudo ./ibeacon 200 67567567567567567567567567567567 1 1 -29
param value
advertisement time in ms 200
UUID 67567567567567567567567567567567
majer number 1
minor number 1
RSSI calibration amount -29

※ パラメータはこれを参考に設定

Beaconの受信

BLEスキャナー

今回はこのアプリを使用 play.google.com

受信できました

距離もImmediate(至近距離)と出てます

Bluetoothバイス名の変更

Beaconを受信できたけど、デバイス名が機械的で認識しずらいので、名前を変更する

/etc/machine-info

/etc/machine-infoを作成し、以下の内容を記述する

PRETTY_HOSTNAME=device-name

Bluetooth serviceのrestart

sudo invoke-rc.d bluetooth restart

確認

再度beaconを送信して確認

バイス名が任意の名前に変更できた

Raspberry Pi Zero WHで、みちびき対応GPS受信機キットを使い位置情報を取得する

秋月電子GPS受信機キットを買ったので、位置情報を取得してみた1

GPS受信機キット

akizukidenshi.com

小型高感度GPSモジュールを使ったGPS受信機キットで、バックアップ電池の電池ボックスとピンヘッダのはんだ付けが必要 ※ バックアップ電池を使わない場合、電池ボックスは不要

配線

Raspberry Pi Zero GPSモジュール
5V 5V
GND GND
RxD TxD
TxD RxD
なし 1PPS

とても基本的なことなんですが、RxDとTxDはクロスさせて接続します。これを間違えて、位置情報が取れず何度も設定を見直し、時間を無駄にしてしまった。。※ 上の写真は間違えた状態です

シリアルの有効化

raspi-config

sudo raspi-config
  • P5 Interfacing Options
  • P6 Serial
  • YES

で、Finish

> ls /dev/serial*
/dev/serial0

/dev/serial0があることを確認

/boot/cmdline.txt

sudo vi /boot/cmdline.txt

もとの/boot/cmdline.txtから、console=serial0,115200の記述を削除する

# dwc_otg.lpm_enable=0 console=tty1 console=serial0,115200 root=PARTUUID=b7e00398-02 rootfstype=ext4 elevator=deadline fsck.repair=yes rootwait modules-load=dwc2,g_ether
dwc_otg.lpm_enable=0 console=tty1 root=/dev/mmcblk0p2 rootfstype=ext4 elevator=deadline fsck.repair=yes rootwait quiet splash plymouth.ignore-serial-consoles

リブート

sudo reboot

動作確認

pyserialのインストール

シリアルモジュールをインストール

pip install pyserial

repl

~$ python
Python 3.6.6 (default, Oct  7 2018, 12:22:23)
[GCC 6.3.0 20170516] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import serial
>>> s = serial.Serial('/dev/serial0', 9600, timeout=10)
>>> s.readline().decode('utf-8')
'$GPGGA,154327.000,,,,,0,1,,,M,,M,,*4F\r\n'

なにか値が取得できた

NMEA0183

モジュールから得られるデータは、NMEA0183に準拠したフォーマットになっている NMEA 0183 - Wikipedia

micropyGPS

取得したデータを扱いやすくするために、NMEAパーサーのmicropyGPSを使う

github.com

repl

Python 3.6.6 (default, Oct  7 2018, 12:22:23)
[GCC 6.3.0 20170516] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import serial
>>> from micropyGPS import MicropyGPS
>>> my_gps = MicropyGPS(9, 'dd')
>>> s = serial.Serial('/dev/serial0', 9600, timeout=10)
>>> for x in s.readline().decode('utf-8'):
...     my_gps.update(x)
...
'GPGGA'
>>> my_gps.latitude
[35.658580566666665, 'N']
>>> my_gps.longitude
[139.74323896666668, 'E']

これでいい感じの位置情報が取得できるようになった